Description

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.

 

Solution

题目要求找数组中所有出现次数多于1/3的元素。并希望算法的时间复杂度为O(n)空间复杂度为O(1)。

初步想来难以以题中要求的复杂度完成，但可以发现隐含条件是，出现次数多于1/3的值最多只有两个（1个或2个）。因此，可以通过设定两个备选值的方式来确定哪两个（也可能是一个）值符合条件。

为什么是设定两个备选而不是一个或其他？

设定两个备选的含义是将数组中的元素看做是3类，分别是：1.与备选值1相等的值；2.与备选值2相等的值；3.与备选值1和2都不相等的值。

 

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class Solution {
public:
    vector<int> majorityElement(vector<int>& nums)
    {
        int a = 0, b = 0;
        int cnta = 0, cntb = 0;
        for(int i = 0; i < (int)nums.size(); i++)
        {
            bool flag = false;
            if(cnta == 0)
            {
                if(cntb != 0 && b == nums[i])
                {
                   cntb++;
                   flag = true;
                }
                else
                {
                    a = nums[i];
                    cnta = 1;
                    flag = true;
                }
            }
            else
            {
                if(a == nums[i])
                {
                    cnta++;
                    flag = true;
                }
                else if(cntb != 0 && b == nums[i])
                {
                    cntb++;
                    flag = true;
                }
                else if(cntb == 0)
                {
                    b = nums[i];
                    cntb = 1;
                    flag = true;
                }
            }
            if(flag == false)
            {
                cnta--;
                cntb--;
            }
        }
        
        cnta = cntb = 0;
        for(int i = 0; i < (int)nums.size(); i++)
        {
            if(nums[i] == a) cnta++;
            if(nums[i] == b) cntb++;
        }
        
        vector<int> ret;
        if(cnta > (int)nums.size() / 3) ret.push_back(a);
        if(b != a && cntb > (int)nums.size() / 3 ) ret.push_back(b);
        return ret;
    }
};