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

在之前的面试中遇到一道问题,题目为找出数组中出现次数超过数组长度一半的元素,最优解法的时间复杂度为\(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中列表的sortcount方法是在底层以C语言实现的,所以速度比for循环等快上非常多。由此可见在Python中多使用内置方法替代循环是十分重要的。但考虑到空间使用情况和不改变原有数据的情况下,方法五依旧是最值得推荐的。


在手机上阅读或分享本文请扫描以下二维码:
By @Zhengyi Yang in
Tags : #python, #counter, #sorting,

Comments

评论功能已关闭。