169.多数元素

题目:169.多数元素

• 示例 1：

输入：nums = [3,2,3]
输出：3

• 示例 2：

输入：nums = [2,2,1,1,1,2,2]
输出：2

• 提示：

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

• 进阶：

进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

思路

要找到数组中的多数元素，并且时间复杂度为 O(n)、空间复杂度为 O(1)，可以使用著名的 Boyer-Moore 投票算法。这种算法利用了多数元素的特性，即多数元素出现的次数大于数组长度的一半。具体步骤如下：

1. 维护一个候选多数元素 result 和它的计数 count。
2. 遍历数组，如果当前元素与 result 相同，则增加 count；如果不同，则减少 count。
3. 如果 count 变为 0，选择当前元素作为新的 result，并将 count 重置为 1。
4. 最后返回 result，它就是数组中的多数元素。

• 时间复杂度:O(n)
• 空间复杂度:O(1)

代码

public int majorityElement(int[] nums) {
    int result = nums[0];
    int conut = 1;
    for (int i = 1; i < nums.length; i++) {
        // 遍历数组，如果当前元素与result相同，则增加count；如果不同，则减少count。
        if (nums[i] == result) {
            conut++;
        } else {
            conut--;
            // 如果count变为0，选择当前元素作为新的result，并将count重置为1。
            if (conut == 0) {
                result = nums[i];
                conut = 1;
            }
        }

    }
    return result;
}