查找数组众数

[编程题]查找数组众数

热度指数：5454 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定一个数组A[n], 定义数组的众数 ( Majority Element) 为数组中出现次数超过 n/2 次的元素, 假设数组A[n]非空且一定存在众数, 请设计算法找到该众数并输出.

输入描述:

一个非空且一定存在众数的整数数组,如: [1,2,2]

输出描述:

输出打印该众数,如: 2

示例1

输入

[1,2,2]

输出

示例2

输入

[3,1,-2,3,1,3,3]

输出

算法知识视频讲解

Python

卷积神经网络哦

python2行搞定评论求一个一行的优雅解法

如果这个众数的数量大于总数的一半那么排序完后中间位置一定是众数

arr = sorted(eval(input()))
print(arr[len(arr)//2])

发表于 2019-12-30 11:36:25 回复(0)

Python

欧巴禾

arr = input() if ',' not in arr:
    arr = arr[1:-1] print(arr) else:
    numbers = list(map(str, arr.split(',')))
    numbers[0] = numbers[0][1:]
    numbers[-1] = numbers[-1][:-1]
    numbers = list(map(int, numbers))
    numbers = sorted(numbers)
    n = len(numbers) print(numbers[int(n//2)])

发表于 2019-09-02 16:34:14 回复(0)

Python

ElonB

""""
众数(Majority Element)超过 n/2 次，提供一种O(n)时间复杂度的算法，
本题时间要求不严格可以排序
"""

if __name__ == "__main__":
    a = eval(input().strip())
    cnt = 0
    ans = a[0]
    for x in a:
        if x == ans:
            cnt += 1
        else:
            cnt -= 1
            if cnt < 0:
                ans = x
                cnt = 1
    print(ans)

发表于 2019-07-12 13:02:31 回复(0)