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