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


#算法#


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个扩展:**求出现次数最多的最大数。也就是说可能有多个数出现的次数都是最多的,取最大的数字,这个很简单,不介绍了。


( 本文完 )