方法一：散列表

由于 0≤ai<n ，我们只需要构造辅助数组 C[0:n] 作为散列表进行计数。

我们设定出现次数最多的为候选元素。

题目告诉我们主元素不一定存在，所以最后我们要检查的候选元素在序列中的出现次数，如果大于 n/2 才能最终确定为主元素。

C代码如下（含测试用例）：

#include <stdio.h>
#include <string.h>

int majorityElement(int *a, int n) {
    int cnts[n + 1];
    memset(cnts, 0, sizeof(cnts));
    int majority = 0, max_cnt = 0;
    for (int i = 0; i < n; ++i) {
        cnts[a[i]]++;
        if (cnts[a[i]] > max_cnt) {
            majority = a[i];
            max_cnt = cnts[a[i]];
        }
    }
    return max_cnt > n / 2 ? majority : -1;
}

int main() {
    int a[] = {0,5,5,3,5,7,5,5};
    int x = majorityElement(a, 8);
    if (x != -1) {
        printf("%d", x);
    }
    return 0;
}

C++代码如下（含测试用例）：

#include <iostream>
#include <vector>
using namespace std;

int majorityElement(vector<int>& nums) {
    const int n = (int)nums.size();
    vector<int>counts(n + 1);
    int majority = 0, max_count = 0;
    for (int i = 0; i < n; ++i) {
        ++counts[nums[i]];
        if (counts[nums[i]] > max_count) {
            majority = nums[i];
            max_count = counts[nums[i]];
        }
    }
    return max_count > n / 2 ? majority : -1;
}

int main() {
    vector<int> a = {0,5,5,3,5,7,5,5};
    int x = majorityElement(a);
    if (x != -1) {
        cout << x;
    }
    return 0;
}

复杂度分析

• 时间复杂度： O(n) 。我们遍历数组一次，对于数组中的每一个元素，计数和比较的时间为常数。
• 空间复杂度： O(n) 。​开辟了大小为 O(n) 的辅助数组。

方法二：摩尔投票算法

如果我们把主元素记为 +1 ，把其他数记为 −1 ，将它们全部加起来，显然和大于 0 ，从结果本身我们可以看出主元素的个数比其他数的总数多。

题目告诉我们主元素不一定存在，所以最后我们要检查的候选元素在序列中的出现次数，如果大于 n/2 才能最终确定为主元素。

C代码如下（含测试用例）：

#include <stdio.h>

int majorityElement(int *a, int n) {
    int candidate = -1;
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
        if (a[i] == candidate) {
            ++cnt;
        } else if (--cnt < 0) {
            candidate = a[i];
            cnt = 1;
        }
    }
    cnt = 0;
    for (int i = 0; i < n; ++i) {
        if (a[i] == candidate) {
            ++cnt;
        }
    }
    return cnt > n / 2 ? candidate : -1;
}

int main() {
    int a[] = {0,5,5,3,5,7,5,5};
    int x = majorityElement(a, 8);
    if (x != -1) {
        printf("%d", x);
    }
    return 0;
}

C++代码如下（含测试用例）：

#include <iostream>
#include <vector>
using namespace std;

int majorityElement(vector<int>& nums) {
    const int n = (int)nums.size();
    int candidate = -1;
    int count = 0;
    for (int i = 0; i < n; ++i) {
        if (nums[i] == candidate) {
            ++count;
        } else if (--count < 0) {
            candidate = nums[i];
            count = 1;
        }
    }
    count = 0;
    for (int i = 0; i < n; ++i) {
        if (nums[i] == candidate) {
            ++count;
        }
    }
    return count > n / 2 ? candidate : -1;
}

int main() {
    vector<int> a = {0,5,5,3,5,7,5,5};
    int x = majorityElement(a);
    if (x != -1) {
        cout << x;
    }
    return 0;
}

复杂度分析

• 时间复杂度： O(n) 。我们遍历数组两次，第一次遍历数组用摩尔投票算法找出最多的元素，第二次遍历数组统计该元素个数，最后检查该元素个数是否大于 n/2 。
• 空间复杂度： O(1) 。只用了常数个辅助变量。

方法三：快速排序 + 中位数

若 A 存在主元素，则该数组的中位数一定是主元素，包括 n 为奇数时的中位数和 n 为偶数时的下中位数和上中位数。

第一步：对 A 进行排序，一般采用快速排序。

第二步：取出中位数，用二分查找统计中位数数量，最后检查中位数个数是否大于 n/2 。

C代码如下：

#include <stdio.h>
#include <stdlib.h>

void swap(int *a, int i, int j){
    int tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
}

int partition(int *a, int p, int r) {
    int x = a[r];
    int i = p - 1;
    for (int j = p; j < r; ++j) {
        if (a[j] <= x) {
            ++i;
            swap(a, i, j);
        }
    }
    swap(a, i + 1, r);
    return i + 1;
}

int randomized_partition(int *a, int p, int r) {
    int i = rand() % (r - p + 1) + p; // 随机选一个作为主元
    swap(a, r, i);
    return partition(a, p, r);
}

void randomized_quicksort(int *a, int p, int r) {
    if (p < r) {
        int q = randomized_partition(a, p, r);
        randomized_quicksort(a, p, q - 1);
        randomized_quicksort(a, q + 1, r);
    }
}

int binary_search_first(int *a, int n, int target){
    int left = 0, right = n - 1;
    while(left <= right) {
        int mid = left + (right - left) / 2;
        if(a[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    if (left != n && a[left] == target) return left;
    return -1;
}

int binary_search_last(int *a, int n, int target){
    int left = 0, right = n - 1;
    while(left <= right) {
        int mid = left + (right - left) / 2;
        if(a[mid] <= target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    if (right != -1 && a[right] == target) return right;
    return -1;
}

int majorityElement(int *a, int n) {
    randomized_quicksort(a, 0, n - 1);
    int median = a[n / 2];
    int first_index = binary_search_first(a, n, median);
    int last_index = binary_search_last(a, n, median);
    int cnt = last_index - first_index + 1;
    return cnt > n / 2 ? median : -1;
}

int main() {
    int a[] = {0,5,5,3,5,7,5,5};
    int x = majorityElement(a, 8);
    if (x != -1) {
        printf("%d", x);
    }
    return 0;
}

复杂度分析：

• 时间复杂度： O(nlog⁡n) 。
• 空间复杂度： O(log⁡n) ，平均情况下递归栈深度为 O(log⁡n) 。

方法四：选择算法 + 中位数

可以用选择算法对方法三进行优化，优化后代码如下：

递归版

C代码如下（含测试用例）：

#include <stdio.h>
#include <stdlib.h>

void swap(int *a, int i, int j){
    int tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
}

int partition(int *a, int p, int r) {
    int x = a[r];
    int i = p - 1;
    for (int j = p; j < r; ++j) {
        if (a[j] <= x) {
            ++i;
            swap(a, i, j);
        }
    }
    swap(a, i + 1, r);
    return i + 1;
}

int randomized_partition(int *a, int p, int r) {
    int i = rand() % (r - p + 1) + p; // 随机选一个作为主元
    swap(a, r, i);
    return partition(a, p, r);
}

void randomized_select(int *a, int p, int r, int i) {
    if (p == r) {
        return;
    }
    int q = randomized_partition(a, p, r);
    int k = q - p + 1;
    if (i == k) {
        return;
    } else if (i < k) {
        randomized_select(a, p, q - 1, i);
    } else {
        randomized_select(a, q + 1, r, i - k);
    }
}

int majorityElement(int *a, int n) {
    randomized_select(a, 0, n - 1, n / 2);
    int median = a[n / 2];
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] == median) {
            cnt++;
        }
    }
    return cnt > n / 2 ? median : -1;
}

int main() {
    int a[] = {0,5,5,3,5,7,5,5};
    int x = majorityElement(a, 8);
    if (x != -1) {
        printf("%d", x);
    }
    return 0;
}

复杂度分析：

• 时间复杂度： O(n) 。
• 空间复杂度： O(log⁡n) ，平均情况下递归栈深度为 O(log⁡n) 。

迭代版

C代码如下（含测试用例）：

#include <stdio.h>
#include <stdlib.h>

void swap(int *a, int i, int j){
    int tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
}

int partition(int *a, int p, int r) {
    int x = a[r];
    int i = p - 1;
    for (int j = p; j < r; ++j) {
        if (a[j] <= x) {
            ++i;
            swap(a, i, j);
        }
    }
    swap(a, i + 1, r);
    return i + 1;
}

int randomized_partition(int *a, int p, int r) {
    int i = rand() % (r - p + 1) + p; // 随机选一个作为主元
    swap(a, r, i);
    return partition(a, p, r);
}

void randomized_select(int *a, int p, int r, int i) {
    int q, k;
    while (1) {
        q = partition(a, p, r);
        k = q - p + 1;
        if (i == k) {
            return;
        } else if (i < k) {
            r = q - 1;
        } else {
            p = q + 1;
            i = i - k;
        }
    }
}

int majorityElement(int *a, int n) {
    randomized_select(a, 0, n - 1, n / 2);
    int median = a[n / 2];
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] == median) {
            cnt++;
        }
    }
    return cnt > n / 2 ? median : -1;
}

int main() {
    int a[] = {0,5,5,3,5,7,5,5};
    int x = majorityElement(a, 8);
    if (x != -1) {
        printf("%d", x);
    }
    return 0;
}

复杂度分析：

• 时间复杂度： O(n) 。
• 空间复杂度： O(1) ，使用了常数个辅助变量。