[LeetCode] 169. Majority Element

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Example 1:
Input: nums = [3,2,3]
Output: 3

Example 2:
Input: nums = [2,2,1,1,1,2,2]
Output: 2

Constraints:
n == nums.length
1 <= n <= 5 * 104
-109 <= nums[i] <= 109

Follow-up: Could you solve the problem in linear time and in O(1) space?

多数元素。

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/majority-element
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题意是给一个数组，有一个数字出现次数超过了数组长度的一半，请求出这个数字。
我给出几个不同解法，其中最优解投票法。

思路一 - 排序

排序，然后直接找数组中间那个数字。
时间O(nlogn)
空间O(1)

JavaScript实现

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    nums.sort();
    return nums[Math.floor(nums.length / 2)];
};

思路二 - hashmap计算每个不同元素出现的次数，返回次数超过数组长度一半的那个数字

时间O(n)
空间O(n)

JavaScript实现

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    let dict = {};
    let breakpoint = nums.length / 2;
    for (let i = 0; i < nums.length; i++) {
        dict[nums[i]] = dict[nums[i]] || 0;
        dict[nums[i]]++;
        if (dict[nums[i]] > breakpoint) {
            return nums[i];
        }
    }
};

Java实现

class Solution {
    public int majorityElement(int[] nums) {
        int half = nums.length / 2;
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (!map.containsKey(nums[i])) {
                map.put(nums[i], 1);
            } else {
                map.put(nums[i], map.get(nums[i]) + 1);
            }
            if (map.get(nums[i]) > half) {
                return nums[i];
            }
        }
        return -1;
    }
}

思路三 - 投票法

意思是先假设数组的第一个元素是要找的元素，设为 candidate，再记录一个变量 count。遍历数组，如果遍历到跟 candidate 不同的数字的时候，count–，当 count == 0 的时候，同时需要换一个 candidate；如果跟 X 一样，就 count++。最后剩下的那个 candidate 就是要找的元素，因为他的出现次数超过了数组的一半所以一定不会被替换掉。

时间O(n)
空间O(1)

Java实现

class Solution {
    public int majorityElement(int[] nums) {
        int count = 0;
        int candidate = nums[0];
        for (int num : nums) {
            if (num != candidate) {
                count--;
            } else {
                count++;
            }
            if (count == 0) {
                candidate = num;
                count++;
            }
        }
        return candidate;
    }
}

JavaScript实现

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function (nums) {
    let count = 0;
    let res = 0;
    let candidate = nums[0];
    for (let num of nums) {
        if (num === candidate) {
            count++;
        } else {
            count--;
        }
        if (count === 0) {
            candidate = num;
            count++;
        }
    }
    return candidate;
};

相关题目

169. Majority Element
229. Majority Element II