如何找到数组中出现次数最多的元素

2014-11-02

之前,有在如何找出数组中重复的元素整理过如何找数组中找到重复出现的数字。

今天遇到这样一个需求,数组中所有的元素的值都在[0,8]之间,且都是整数,我需要找出出现次数最多的元素。这个问题可以用如何找出数组中重复的元素提出的方法来解决,我是使用位向量的方法来解决的,算法的时间复杂度为[latex]O(n) [/latex],代码如下:

# !/usr/bin/env python
# -*- encoding:utf-8 -*-

arr = [0, 2, 5, 6, 1, 0, 1, 4, 1]

def get_max_occur_number(arr):
    vector = [0] * len(arr) 
    for n in arr:
        vector[n] += 1
    max_occur_number = max(vector) # vector中的最大值
    return vector.index(max_occur_number)  # 最大值的位置


if __name__ == '__main__':
    print get_max_occur_number(arr)

运行结果输出1

我在谷歌上搜索了该问题,发现这个问题的两个扩展。

第1个扩展:要求时间复杂度为[latex]O(n)[/latex],且不使用辅助空间。在开源中国社区的讨论区中,一道数组面试题-不能使用辅助空间找重复次数的数给出了多种解法,都很有技巧性,甚至是太有技巧了,不过有一个解法简单:

for i in lst:
  lst[i%100] += 100

lst = map(lambda x: x/100, lst)

print lst.index(max(lst))

添加到我上面的代码:

# !/usr/bin/env python
# -*- encoding:utf-8 -*-

def get_max_occur_number(arr):
    for i in arr:
        arr[i%100] += 100 # 或者arr[i] += 100
    print arr
    arr = map(lambda x: x/100, arr) # arr每个元素除以100
    print arr
    return arr.index(max(arr))


if __name__ == '__main__':
    arr = [0, 2, 5, 6, 1, 0, 1, 4, 1]  # 每个元素是整数
    print arr
    print get_max_occur_number(arr)

其实,就是在原先的数组中使用位向量的方法。上面代码的运行结果:

[0, 2, 5, 6, 1, 0, 1, 4, 1]
[200, 302, 105, 6, 101, 100, 101, 4, 1]
[2, 3, 1, 0, 1, 1, 1, 0, 0]
1

[200, 302, 105, 6, 101, 100, 101, 4, 1]中前9个元素(因为数组中所有的元素的值都在[0,8]之间)每个元素的个位数和十位数删掉,就是相应的数字的出现次数。

第2个扩展:求出现次数最多的最大数。也就是说可能有多个数出现的次数都是最多的,取最大的数字,这个很简单,不介绍了。

( 完 )