leetcode-169 Majority Element

169. Majority Element

Description

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.

Example 1:

1
2
Input: [3,2,3]
Output: 3

Example 2:

1
2
Input: [2,2,1,1,1,2,2]
Output: 2

Analyse

找出一个长为$n$的数组中出现次数大于⌊ n/2 ⌋的数

$n$不为0
majority element一定存在

第一种方法，majority element的出现次数大于一半，先排序，然后直接取中间的元素，时间复杂度主要是sort的，平均时间复杂度为$O(Nlog(N))$

The C standard doesn’t talk about its complexity of qsort. The new C++11 standard requires that the complexity of sort to be O(Nlog(N)) in the worst case. Previous versions of C++ such as C++03 allow possible worst case scenario of O(N^2). Only average complexity was required to be O(N log N).

1
2
3
4
5
int majorityElement(vector<int>& nums)
{
    sort(nums.begin(), nums.end());
    return nums[nums.size() / 2];
}

结果被大佬们虐成渣了

1
2
3
Runtime: 28 ms, faster than 28.19% of C++ online submissions for Majority Element.

Memory Usage: 11.1 MB, less than 80.66% of C++ online submissions for Majority Element.

第二种方法，计数法，找个map计算元素出现次数，输出次数大于一半的元素，时间复杂度$O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int majorityElement(vector<int>& nums)
{
    unordered_map<int, int> map;

    for(int a : nums)
    {
        if (++map[a] > (nums.size() / 2))
        {
            return a;
        }
    }

    return -1;
}

比前面那种方法快了一点，但在leetcode上还是不够快，

1
2
3
Runtime: 24 ms, faster than 48.33% of C++ online submissions for Majority Element.

Memory Usage: 11 MB, less than 96.80% of C++ online submissions for Majority Element.

加上一些优化代码后，在leetcode上已经是最快了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
static int x=[](){
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    return 0;
}();

class Solution {
public:
    int majorityElement(vector<int>& nums)
    {
        unordered_map<int, int> map;

        for(int a : nums)
        {
            if (++map[a] > (nums.size() / 2))
            {
                return a;
            }
        }

        return -1;
    }
};
1
2
3
Runtime: 4 ms, faster than 100.00% of C++ online submissions for Majority Element.

Memory Usage: 11.1 MB, less than 74.76% of C++ online submissions for Majority Element.

第三种方法，来自leetcode，由于majority element的个数大于一半，对数组中不一样的元素两两删除，剩下的就是majority element

直接对vector删除元素很耗时，使用stack来模拟这个删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int majorityElement(vector<int>& nums)
{
    stack<int> tony;

    for(int a : nums)
    {
        if (tony.empty() || a == tony.top())
        {
            tony.push(a);
        }
        else
        {
            tony.pop();
        }
    }

    return tony.top();
}
1
2
3
Runtime: 8 ms, faster than 99.91% of C++ online submissions for Majority Element.

Memory Usage: 11.7 MB, less than 5.43% of C++ online submissions for Majority Element.

第四种方法，分治法，先把数组一分为2，从左右两边获取majority element候选，最终的结果就从这两个候选产生，计算这两个候选出现的次数，出现次数多的为最终的majority element（题目已假定majority element一定存在）

Reference

  1. https://www.geeksforgeeks.org/c-qsort-vs-c-sort/