主数

主数是指在序列中出现次数超过一定比例的数，假设序列长度为n，则出现次数大于n/k的数最多有k-1个。

求主数使用投票算法，时间复杂度为$O(n)$，空间复杂度为$O(1)$。

找出数组arr[n]中出现次数大于n/2的数（最多有1个），pick为候选的数，vote表示其被抵消之后的票数（初始化为0）。

算法分为两个步骤，第一步选出pick，数组的主数如果有，必然是pick，否则就是没有；然后还需要第二步，判断pick出现次数是否真的大于n/k。

for (int i = 0; i < n; i++) {
    if (vote > 0 && arr[i] == pick) {  // 如果抵消后票数大于0，pick有效，且当前数等于pick，票数++
        vote++;
    } else if (vote == 0) {  // 如果抵消后票数等于0，pick失效，将当前数作为新的pick
        pick = arr[i];
        vote++;
    } else {  // 如果抵消后票数大于0，pick有效，但当前数不等于pick，票数--
        vote--;
    }
}

int cnt = 0;
for (int i = 0; i < n; i++) {
    if (arr[i] == pick)
        cnt++;
}
if (cnt*2 > n)
    // 获得主数pick

找出数组arr[n]中出现次数大于n/3的数（最多有2个），pick1 & pick2为候选的数，vote1 & vote2表示其被抵消之后的票数（初始化为0）。

算法分为两个步骤，第一步选出pick1 & pick2，数组的主数如果有，必然在pick1 & pick2中，否则就是没有；然后还需要第二步，判断pick1 & pick2出现次数是否真的大于n/k。

for (int i = 0; i < n; i++) {
    if (vote1 > 0 && arr[i] == pick1) {  // 如果抵消后票数大于0，pick有效，且当前数等于pick，票数++
        vote1++;
    } else if (vote2 > 0 && arr[i] == pick2) {
        vote2++;
    } else if (vote1 == 0) {  // 如果抵消后票数等于0，pick失效，将当前数作为新的pick
        pick1 = arr[i];
        vote1++;
    } else if (vote2 == 0) {
        pick2 = arr[i];
        vote2++;
    } else {  // 如果抵消后票数大于0，pick有效，但当前数不等于pick，票数--
        vote1--;
        vote2--;
    }
}

int cnt1 = 0, cnt2 = 0;
for (int i = 0; i < n; i++) {
    if (arr[i] == pick1)
        cnt1++;
    else if (arr[i] == pick2)
        cnt2++;
}
if (cnt1*3 > n)
    // 获得主数pick1
else if (cnt2*3 > n)
    // 获得主数pick2

---