剑指offer系列:x寻找数组中出现次数超过一半的数

剑指offer 029题

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

HashMap的方式

利用空间复杂度O(n)的HashMap作为辅助空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

def MoreThanHalfNum_Solution(self, numbers):
    HashMap = dict()
    for key in numbers:
        if key in HashMap:
            HashMap[key] += 1
        else:
            HashMap[key] = 1
    result = 0
    temp = 0
    for k, v in HashMap.items():
        if v > temp:
            temp = v
            result = k
    if temp <= len(numbers)/2:
        return 0
    return result

在用这种方法实现的时候,设计到了python dictionary的一些特点了,在这道题的背景下,我们期望找出HashMap这个dict中value最大项所对应的key值,这里我用了一个for循环来解决,这似乎不够pythonic,是否有更加方便的方式呢?其实问题可以重新定义一下,python的dict数据类型按照value值的大小进行排序.这里用到了python的内建函数sorted,下面举例子来说明一下:

1
2

example_dict = {'a':3,'c':2,'b':1}
print(example_dict)

{'a': 3, 'c': 2, 'b': 1}

1

sorted(example_dict.items(), key= lambda item:item[1])

[('b', 1), ('c', 2), ('a', 3)]

1

sorted(example_dict.items(), key= lambda item:item[1],reverse=True)

[('a', 3), ('c', 2), ('b', 1)]

同理,如果按照key进行排序的话可以写作,reverse这个参数决定是顺序还是逆序,同时需要注意的是,sorted会生成一个新的dict,而原始的example_dict中的顺序没有被改变.

1

sorted(example_dict.items(), key= lambda item:item[0])

[('a', 3), ('b', 1), ('c', 2)]

数组特点查找

剑指上的第二种解法,定义了两个变量num和count,从头在数组中选取一个数,令其为num,并置count为1,开始遍历数组,如果遇到的新项与num相等则count+1,否则count-1,若count已经是0的情况下,则num换为当前的数,count重新置为0.直到遍历完成,若count此时大于0,则num即为所求结果.但是在这里需要进一步检查,是否num是在数据中超过一半,因此还需要再进行一次遍历(这里还应该有一次遍历能够解决的方案么?),代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

def MoreThanHalfNum_Solution(self, numbers):
    if len(numbers) <= 0 or numbers is None:
        return None
    num = numbers[0]
    count = 0
    for k, v in enumerate(numbers,1):
        if v == num:
            count += 1
        elif v != num and count == 0:
            num = v
            count = 1
        else:
            count -= 1
    if count <= 0:
        return 0
    time = 0
    for i in numbers:
        if i == num:
            time += 1
    if time * 2 <= len(numbers):
        return 0
    return num

细心读代码的同学应该能够看到这里也用了一个python的trick在之前的博客当中也有提到的enumerate,因为我们令num为numbers[0],此时再进行遍历的时候我们期望从numbers[1]开始向后遍历,如果采用range的形式也未尝不可,可以写作for iteration in range(1, len(numbers)-1),然后通过numbers[iteration]来取值.显然相比于上面的实现方式要显得繁琐,代码的可阅读性也不够好.因此当你想要从某个index遍历list的时候不要忘记enumerate这个实现方式.

参考链接:

• https://docs.python.org/3/howto/sorting.html
• http://www.runoob.com/python/python-func-sorted.html
• http://www.cnblogs.com/linyawen/archive/2012/03/15/2398292.html

下一篇：线性回归的三种比对方式