leetcode 169 Majority Element 冰山查询

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

思路:

Find k different element, and “remove” them as a group, the remaining element must be the element that appears more than ⌊n/k⌋ times. (Detailed explanation is given in comment)

In this problem, k equals to 2.

Thus we “remove” each pair of 2 different elements, and the remaining element that do not have its counterpart is the desired element.

时间复杂度O(n)空间复杂度O(1)的算法呢? 实际上,早在91年就有人专门就这个问题发表了论文,介绍了一种线性时间的算法: Majority Vote Algorithm。通过名字就可以看出,这个算法是专门用来解决这个问题的。而由于作者是J Moore (目前是Utexas的计算机系主任),这个算法有时候也会被称为Moore’s Voting Algorithm (当然这个Moore并不是提出Moore’s Law的那个Gordon Moore)。

算法的基本思想非常简洁: 每次都找出一对不同的元素,从数组中删掉,直到数组为空或只有一种元素。 不难证明,如果存在元素e出现频率超过半数,那么数组中最后剩下的就只有e。当然,最后剩下的元素也可能并没有出现半数以上。比如说数组是[1, 2, 3],最后剩下的3显然只出现了1次,并不到半数。排除这种false positive情况的方法也很简单,只要保存下原始数组,最后扫描一遍验证一下就可以了。

现在来分析一下复杂度。删除元素可以在常数时间内完成,但找不同元素似乎有点麻烦。实际上,我们可以换个角度来想,用一个小trick来重新实现下该算法。

在算法执行过程中,我们使用常量空间实时记录一个候选元素c以及其出现次数f(c),c即为当前阶段出现次数超过半数的元素。在遍历开始之前,该元素c为空,f(c)=0。然后在遍历数组A时,

如果f(c)为0,表示当前并没有候选元素,也就是说之前的遍历过程中并没有找到超过半数的元素。那么,如果超过半数的元素c存在,那么c在剩下的子数组中,出现次数也一定超过半数。因此我们可以将原始问题转化为它的子问题。此时c赋值为当前元素, 同时f(c)=1。
如果当前元素A[i] == c, 那么f(c) += 1。(没有找到不同元素,只需要把相同元素累计起来)
如果当前元素A[i] != c,那么f(c) -= 1 (相当于删除1个c),不对A[i]做任何处理(相当于删除A[i])

如果遍历结束之后,f(c)不为0,那么再次遍历一遍数组,记录c真正出现的频率,从而验证c是否真的出现了超过半数。上述算法的时间复杂度为O(n),而由于并不需要真的删除数组元素,我们也并不需要额外的空间来保存原始数组,空间复杂度为O(1)。实际上,在Moore大牛的主页上有针对这个算法的一个演示,感兴趣的同学可以直接移步观看。

这个问题看上去已经完美的解决了。

二、更一般的情况呢?

那么,如果我们想找的并不是超过半数的元素,而是出现频率超过一定频率的元素都要找出来,是否也存在一个类似的线性时间的算法呢?答案是肯定的。实际上,这一类从特定的数据集中找出出现频率超过某个阈值的元素的问题,有一个形象的名字叫做Iceberg query,或者叫做host list分析。而Richard Karp 老爷子当年就专门写了一篇论文来讨论这种一般性问题的解决方案,而通过下文的介绍,大家也可以发现,Karp的方案应该也是受到了Moore的算法的启发。

首先还是看一下问题的形式化定义吧:

对于一个序列 以及一个在(0,1)之间的实数。假定表示元素的出现频率,我们需要找到所有满足的元素。

原帖连接:

https://leetcode.com/discuss/19151/solution-computation-space-problem-can-extended-situation

http://m.blog.csdn.net/blog/wenyusuran/40780253

解决方案:

class Solution {
public:
int majorityElement(vector<int>& nums)
{
int size = nums.size();
int vote = 0;
int count = 0; for(int i = 0;i < size;i++)
{
if(count == 0)
{
vote = nums[i];
count = 1;
}
else
{
if(vote == nums[i])
count++;
else
count--;
}
}
return vote;
}
};

STL解决方案:

int majorityElement(vector<int> &num)
{
map<int, int>count;
for (vector<int>::iterator i = num.begin(); i != num.end();i++)
{
if ( (++count[*i]) > num.size() / 2)
return *i; }
}

c语言:

int majorityElement(int num[], int n)
{
int cnt = 0, res;
for (int i = 0; i < n; ++i)
{
if (cnt == 0) res = num[i];
if (res == num[i]) ++cnt;
else --cnt;
}
return res;
}

python解决方案:

class Solution:
# @param {integer[]} nums
# @return {integer}
def majorityElement(self, nums):
count = {}
for i in nums:
if i not in count:
count[i] = 0
count[i] += 1
if count[i] > len(nums)/2:
return i
上一篇:python 学习笔记7(类/对象的属性;特性,__getattr__)


下一篇:MD5加密方式