问题描述
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.
出自leetcode第169题,最直接的解法如下:
排序取中
首先想到的是快排后取中间数字的方法,实现如下:
1 |
/*time outed for leetcode*/ |
提交后未通过,超时了。看来排序算法的复杂度太高,只能用线性时间排序的办法了,于是查到了下面的算法。
Moor’s voting algorithm
这是一个在线性时间内找出出现超过一半的数字的算法。主要思想是利用结果数字频率最高的特点:将该数字和其他数字一一对应之后,由于这个数字出现频率超过一半,该数字一定还会有剩余。而我们将一一对应的数字删除之后剩下的那个数一定就是所求数字。
算法实现时,我们只需要扫一遍,如果发现两个不同的数字,就对这两个数字消除(将这两个数字的出现频率分别减一即可)。我们只需要维护一个数(遍历过程中出现频率最高的这个数)的count值即可。
代码实现非常简洁,入下:
1 |
int majorityElement(int* nums, int numsSize) { |
Moor’s voting算法时间复杂度为$O(n)$,空间复杂度$O(1)$。
近期评论