给定含有 n 个元素的多重集合 S ，每个元素在 S 中出现的次数称为该元素的重数。多重 集 S 中重数最大的元素称为众数。 例如， S={1 ， 2 ， 2 ， 2 ， 3 ， 5} 。 多重集 S 的众数是 2 ，其重数为 3 。 对于给定的由 n 个自然数组成的多重集 S，编程计算 S 的众数及其重数。 数据输入： 输入数据由文件名为 input.txt 的文本文件提供。 文件的第 1 行多重集 S 中元素个数 n ；接下来的 n 行中，每行有一个自然数。

好的，这道题可以使用哈希表来解决。我们可以遍历一遍多重集合 S，统计每个数字出现的次数，然后找到出现次数最多的数字即为众数。

以下是 Python 代码实现：

# 读取输入文件
with open('input.txt', 'r') as f:
    n = int(f.readline().strip())
    S = []
    for i in range(n):
        S.append(int(f.readline().strip()))

# 统计每个数字出现的次数
count = {}
for num in S:
    count[num] = count.get(num, 0) + 1

# 找到出现次数最多的数字
mode = max(count, key=count.get)
mode_count = count[mode]

# 输出结果
print("众数为：", mode)
print("重数为：", mode_count)

以上代码中，`count` 是一个字典，用于记录每个数字出现的次数。`count.get(num, 0)` 表示获取数字 `num` 的计数，若该数字不存在，则返回默认值 0。`max(count, key=count.get)` 表示在字典 `count` 中寻找值最大的键，即出现次数最多的数字。

相关问题

众数问题。给定含有n个元素的多重集合S，每个元素在S中出现的次数称为该元素的重数，多重集合S中重数最大的元素称为众数。对于给定的由n个自然数组成的多重集S

，设计一个时间复杂度为O(n)的算法，找到其众数。

解法：使用摩尔投票算法。该算法的基本思想是，遍历数组，维护一个候选众数和一个计数器。初始时，候选众数为第一个元素，计数器为1。依次遍历数组中的元素，如果当前元素等于候选众数，则计数器加1，否则计数器减1。当计数器减为0时，将当前元素设为候选众数，并将计数器设为1。遍历结束后，候选众数即为众数。

证明：假设多重集合S中的众数为x，其重数为m，其他元素的重数之和为n-m。由于x的重数大于其他元素的重数之和，因此在遍历数组时，每次遇到x都会将计数器加1，而每次遇到其他元素都会将计数器减1。因此，当遍历结束时，计数器的值大于0，说明x的重数大于其他元素的重数之和，即x为众数。

时间复杂度：该算法只需要遍历一遍数组，时间复杂度为O(n)。

代码实现：

int majorityElement(vector<int>& nums) {
int candidate = nums[0];
int count = 1;
for (int i = 1; i < nums.size(); i++) {
if (nums[i] == candidate) {
count++;
} else {
count--;
if (count == 0) {
candidate = nums[i];
count = 1;
}
}
}
return candidate;
}

给定含有n个元素的多重集合S，每个元素在S中出现的次数称为该元素的重数。多重集S中最大的元素称为众数。给定一个n个自然数组成的多重集合S，设计算法求其众数和重数。

为了在一个包含n个元素的多重集合S中找到众数及其重数，可以使用哈希表或计数排序来解决这个问题。这里是一个简单的步骤描述：

1. **初始化**：创建两个变量，一个用于存储最大元素（初始值设为第一个元素），另一个用于存储最大元素的计数（初始值设为1）。同时，初始化一个空的哈希表或使用一个大小足够大的数组记录每个元素的出现次数。

2. **遍历数组**：对于数组S中的每个元素e，执行以下操作：
- 如果e等于当前的最大元素，则将最大元素的计数加一。
- 否则，如果哈希表或数组中存在e，并且它的计数大于最大元素的计数，更新最大元素和最大计数。
- 如果哈希表或数组中不存在e，添加e到哈希表或数组，并将其计数设置为1。

3. **查找众数**：遍历结束后，哈希表或数组中的某个元素可能是众数，因为它有最大的计数。遍历一次即可找到并返回这个元素及其对应的计数作为重数。

4. **验证结果**：确认最大元素的计数是否只有一份，如果是，则它就是唯一的众数；如果有多个元素计数相等且都是最大值，那么它们都是众数。

示例代码（Python）：
def find_mode_and_count(S):
    counts = {}
    max_element = S[0]
    max_count = 1

    for num in S:
        if num in counts:
            counts[num] += 1
        else:
            counts[num] = 1
        
        if counts[num] > max_count:
            max_element = num
            max_count = counts[num]

    mode = [num for num, count in counts.items() if count == max_count]
    
    return max_element, max_count, mode if len(mode) > 1 else max_element

# 使用示例
S = [1, 1, 2, 3, 3, 3, 4, 4, 5]
mode, count, possible_modes = find_mode_and_count(S)