给定含有n个元素的多重集合s，每个元素在s中出现的次数称为该元素的重数。多重集s中重数最大的元素称为众数。例如，s={1，2，2，2，3，5}。多重集s的众数是2，其重数为3。对于给定的由n 个自然数组成的多重集s，计算s的众数及其重数。如果出现多个众数，请输出最小的那个。

此题是求给定含有n个元素的多重集合s，每个元素在s中出现的次数为该元素的重数。多重集合s中重数最大的元素称为众数。例如，s={1,2,2,2,3,5}。多重集合s的众数是2，其重数为3。对于给定的由n个自然数组成的多重集合s，计算s的众数及其重数。如果出现多个众数，则输出最小的那个。

相关问题

众数问题。给定含有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中重数最大的元素称为众数，如s = {1,2,2,2,5,3}。多重集s的众数是2，其重数为3

以下是Python实现：

def mode(s):
    """
    返回多重集合s的众数和其重数
    """
    count = {}
    for x in s:
        if x in count:
            count[x] += 1
        else:
            count[x] = 1
    max_count = max(count.values())
    modes = []
    for x in count:
        if count[x] == max_count:
            modes.append(x)
    return modes, max_count

s = [1, 2, 2, 2, 5, 3]
modes, max_count = mode(s)
print("众数为：", modes, "重数为：", max_count)

输出结果为：

众数为： [2] 重数为： 3