找出数组中出现次数超过数组长度一半的元素

在之前的面试中遇到一道问题，题目为找出数组中出现次数超过数组长度一半的元素，最优解法的时间复杂度为$O(n)$，空间复杂度为$O(1)$，在此总结一下。

首先说说时间复杂度为$O(n^2)$的解法。非常简单，历遍这个数组，对每个元素统计该元素出现的次数。若出现次数超过一半的则返回，不然返回None。这样需要的额外空间为$O(1)$，Python可以实现如下：

def moreThanHalf1(l):
    for elem in l:
        if l.count(elem) > len(l) / 2:
            return elem
    return None

若数组中重复的元素较多，使用set可以起到一定优化作用，但也需要更多的内存空间：

def moreThanHalf1_1(l):
    for elem in set(l):
        if l.count(elem) > len(l) / 2:
            return elem
    return None

不难想到，使用排序可以改进以上算法，做到$O(n\cdot\log(n))$的时间复杂度。排序后我们不需要嵌套循环数组以得到出现次数，因为相同的元素已经被排列在一起了。如果允许修改原来的数组，则空间复杂度也为$O(1)$，Python可以实现为：

def moreThanHalf2(l):
    size = len(l)
    l.sort()
    for i in xrange(size):
        if i == 0 or l[i - 1] != l[i]:
            counter = 1
        else:
            counter += 1
        if counter > size / 2:
            return l[i - 1]
    return None

不过再仔细一想的话可以发现，如果出现次数超过数组长度一半的元素存在，则它一定出现在排好序的数组的一半的位置，所以将以上代码改进为：

def moreThanHalf3(l):
    if len(l) > 0:
        l.sort()
        if l.count(l[len(l) / 2]) > len(l) / 2:
            return l[len(l) / 2]
    return None

接下来，需要考虑时间为$O(n)$的算法。如果允许使用$O(n)$的额外空间，可以用HashTable记录每个元素出现的次数，这样便可简单的达到要求。在Python中，借助现成的Counter函数：

from collections import Counter
def moreThanHalf4(l):
    if len(l) > 0:
        (candidate, counter), = Counter(l).most_common(1)
        if counter > len(l) / 2:
            return candidate
    return None

也可以自己实现Counter的功能：

def moreThanHalf4_2(l):
    if len(l) > 0:
        counter = {}
        for elem in l:
            if elem in counter:
                counter[elem] += 1
            else:
                counter[elem] = 1
        candidate, count = max(counter.iteritems(), key=lambda x: x[1])
        if count > len(l) / 2:
            return candidate
    return None

以上几种方法都不难得到，但要找出更好的解决方案便需要再仔细观察一下问题的性质了。考虑到常用的方法是将问题逐渐缩小，若出现次数超过数组长度一半的元素存在，则删去两个互不相同的元素后，该元素出现的次数依旧超过数组长度的一半。但由于要保留原数组做检测，不可以在原来的数组上进行删除元素的操作，依然需要O(n)的空间来保存元素是否被删除，所以需要一种方法来替代删除的操作。其实只需要额外的两个变量即可实现，一个用来保持当前的候选元素，一个用来计数。如果下一个元素和候选元素相同则次数加1，不同减1，如果次数变为0则保存下一个元素为候选元素,最终情况是出现次数最多的元素最终被保存下来，然后检查是否超过半数。

def moreThanHalf5(l):
    counter = 0
    for elem in l:
        if counter == 0:
            candidate = elem
            counter = 1
        elif candidate == elem:
            counter += 1
        else:
            counter -= 1
    if l.count(candidate) > len(l) / 2:
        return candidate
    return None

这种方法应该会有比较优秀的表现，接着用timeit函数测试一下以上几种方法的运行时间。首先，测试中使用的是一个长度为$10^6$的list，其中的每个元素为1-100之间的随机整数。因为使用了排序的方法会改变list中的内容，在运行测试前，生成的随机list被复制成了几份。除此之外，由于方法一运行速度过于慢，无法在合理的时间内运行完，只比较后面几种方法。

timeit -n10 moreThanHalf1_1(l1)
10 loops, best of 3: 1.57 s per loop

timeit -n10 moreThanHalf2(l2)
10 loops, best of 3: 184 ms per loop

timeit -n10 moreThanHalf3(l3)
10 loops, best of 3: 26 ms per loop

timeit -n10 moreThanHalf4(l4)
10 loops, best of 3: 254 ms per loop

timeit -n10 moreThanHalf4_2(l4)
10 loops, best of 3: 112 ms per loop

timeit -n10 moreThanHalf5(l5)
10 loops, best of 3: 79.2 ms per loop

由结果可见，最快的为方法三。这和之前分析的并不相同，这是因为Python中列表的sort和count方法是在底层以C语言实现的，所以速度比for循环等快上非常多。由此可见在Python中多使用内置方法替代循环是十分重要的。但考虑到空间使用情况和不改变原有数据的情况下，方法五依旧是最值得推荐的。

在手机上阅读或分享本文请扫描以下二维码：

找出数组中出现次数超过数组长度一半的元素

Comments