Major Element

Posted on | In

问题描述

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
2
3
4
5
/*time outed for leetcode*/
int majorityElement_qkst(int* nums, int numsSize) {
    quick_sort(nums, 0, numsSize-1);
    return nums[numsSize/2];
}

提交后未通过，超时了。看来排序算法的复杂度太高，只能用线性时间排序的办法了，于是查到了下面的算法。

Moor’s voting algorithm

这是一个在线性时间内找出出现超过一半的数字的算法。主要思想是利用结果数字频率最高的特点：将该数字和其他数字一一对应之后，由于这个数字出现频率超过一半，该数字一定还会有剩余。而我们将一一对应的数字删除之后剩下的那个数一定就是所求数字。

算法实现时，我们只需要扫一遍，如果发现两个不同的数字，就对这两个数字消除（将这两个数字的出现频率分别减一即可）。我们只需要维护一个数（遍历过程中出现频率最高的这个数）的count值即可。

代码实现非常简洁，入下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int majorityElement(int* nums, int numsSize) {
    int condidate;
    int count = 0;
    for (int i = 0; i < numsSize; ++i)
    {
        if (count == 0)
        {
            condidate = nums[i];
            count = 1;
        }
        else if (nums[i] == condidate)
        {
            count++;
        }
        else {
            count--;
        }    
    }
    return condidate; 
}

Moor’s voting算法时间复杂度为$O(n)$，空间复杂度$O(1)$。

0%