题解

题面描述

题目要求在一个大小为$n$的数组$nums$中寻找多数元素，即出现次数大于$⌊n/2⌋$的元素。
可以保证数组非空且多数元素一定存在。

思路

由于多数元素出现次数超过数组长度的一半，因此可以采用Boyer-Moore 投票算法。
该算法的核心思路是：

• 定义候选元素和计数器。
• 遍历数组，当计数器为$0$时，将当前元素设为候选元素，并将计数器设为$1$；
• 如果后续元素与候选元素相同，则计数器加$1$，否则计数器减$1$。
• 最终候选元素就是多数元素。

该算法时间复杂度为$O(n)$，空间复杂度为$O(1)$。

代码分析

• 初始化：定义变量$candidate$和$count$。
• 遍历数组：若$count$为$0$，更新$candidate$为当前元素；若当前元素与$candidate$相同则$count++$，否则$count--$。
• 输出：遍历结束后，$candidate$即为所求的多数元素。

算法本质上通过“抵消”策略，使得最后剩下的候选元素必定为多数元素。

C++

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

class Solution {
public:
    // 返回数组中的多数元素
    int majorityElement(vector<int>& nums) {
        int candidate = 0; // 候选元素
        int count = 0;     // 计数器
        for (int num : nums) { // 遍历数组
            if (count == 0) { // 如果计数器为0，则更新候选元素
                candidate = num;
                count = 1;
            } else if (num == candidate) { // 当前元素与候选元素相同，计数器加1
                count++;
            } else { // 否则，计数器减1
                count--;
            }
        }
        return candidate;
    }
};

int main() {
    int x;
    vector<int> nums;
    // 读取所有输入数字，注意ACM模式下输入由空格或者换行分隔
    while (cin >> x) {
        nums.push_back(x);
    }
    Solution sol;
    cout << sol.majorityElement(nums) << endl;
    return 0;
}

Python

class Solution:
    def majorityElement(self, nums):
        # 初始化候选元素和计数器
        candidate = None  # 候选元素
        count = 0         # 计数器
        # 遍历数组中的每个数字
        for num in nums:
            if count == 0:
                candidate = num  # 当计数器为0时，更新候选元素
                count = 1
            elif num == candidate:
                count += 1       # 当前数字与候选元素相同，计数器加1
            else:
                count -= 1       # 不同则计数器减1
        return candidate

if __name__ == '__main__':
    import sys
    # 读取输入，以空格或换行分隔所有数字
    data = sys.stdin.read().strip().split()
    nums = list(map(int, data))
    sol = Solution()
    print(sol.majorityElement(nums))

Java

import java.util.Scanner;
import java.util.ArrayList;

public class Main {
    static class Solution {
        // 返回数组中的多数元素
        public int majorityElement(int[] nums) {
            int candidate = 0; // 候选元素
            int count = 0;     // 计数器
            for (int num : nums) { // 遍历数组
                if (count == 0) {
                    candidate = num; // 当计数器为0时，更新候选元素
                    count = 1;
                } else if (num == candidate) {
                    count++; // 当前数字与候选元素相同，计数器加1
                } else {
                    count--; // 不同则计数器减1
                }
            }
            return candidate;
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        ArrayList<Integer> list = new ArrayList<>();
        // 读取所有输入数字
        while (sc.hasNextInt()) {
            list.add(sc.nextInt());
        }
        int n = list.size();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = list.get(i);
        }
        Solution sol = new Solution();
        System.out.println(sol.majorityElement(nums));
        sc.close();
    }
}

题目内容

给定一个大小为 $n$ 的数组 $nums$ ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 $⌊ n/2 ⌋$的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素

输入描述

输入一个数组

输出描述

输出一个整数表示其中的多数元素

样例1

输入

3 2 3

输出

3

样例2

输入

2 2 1 1 1 2 2

输出

2

提示

• $n == nums.length$
• $1 <= n <= 5 * 10^4$
• $-10^9 <= nums[i] <= 10^9$