leetcode/229.cpp at master · Bright1992/leetcode · GitHub

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
//
// Created by Bright on 2016/12/27.
//

#include <vector>

using namespace std;

vector<int> majorityElement(vector<int> &nums) {
    int len = nums.size();
    vector<int> candidate(3, 0), valid(3, 0), cnt(3, 0), ncnt(3, 0);
    int flag = 0;
    for (int i = 0; i < len; ++i) {
        for (int j = 0; j < 3; ++j) {
            if (valid[j] == 1 && candidate[j] == nums[i]) {
                cnt[j]++;
                flag = 1;   //found
            }
            if (valid[j] == 1 && candidate[j] != nums[i]) {
                ncnt[j]++;
                if (cnt[j] * 2 < ncnt[j]) {
                    valid[j] = cnt[j] = ncnt[j] = 0;
                }
            }
        }
        if (flag == 0) {    //not found
            for (int j = 0; j < 3; ++j)
                if (valid[j] == 0) {
                    valid[j] = 1;
                    candidate[j] = nums[i];
                    cnt[j] = 1;
                    break;
                }
        }
        flag = 0;
    }
    cnt[0] = cnt[1] = cnt[2] = 0;
    for (int i = 0; i < len; ++i)
        for (int j = 0; j < 3; ++j)
            if (valid[j] == 1 && nums[i] == candidate[j])
                cnt[j]++;
    vector<int> ret;
    for (int j = 0; j < 3; ++j)
        if (valid[j] == 1 && cnt[j] > len / 3)
            ret.push_back(candidate[j]);
    return ret;
}

#define NAN 0x80000000

vector<int> majorityElement_opt(vector<int> &nums) {
    if (nums.size() == 0) return vector<int>(0);
    int a = NAN, b = NAN + 1, cnta = 0, cntb = 0;
    for (auto n:nums) {
        if (a == n)
            cnta++;
        else if (b == n)
            cntb++;
        else {
            if (cnta == 0) {
                cnta = 1;
                a = n;
            } else if (cntb == 0) {
                cntb = 1;
                b = n;
            } else {
                cnta--;
                cntb--;
            }
        }
    }
    vector<int> ret;
    cnta = cntb = 0;
    for (auto n:nums) {
        if (a == n) cnta++;
        if (b == n) cntb++;
    }
    if (cnta > nums.size() / 3) ret.push_back(a);
    if (cntb > nums.size() / 3) ret.push_back(b);
    return ret;
}