LeetCode169——求众数

我的LeetCode代码仓：https://github.com/617076674/LeetCode

原题链接：https://leetcode-cn.com/problems/majority-element/description/

题目描述：

知识点：哈希表、分治算法、位运算、摩尔投票法

思路一：用哈希表记录各个数字出现的次数

时间复杂度和空间复杂度均是O(n)。

JAVA代码：

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

LeetCode解题报告：

思路二：排序后直接返回最中间的数

时间复杂度是O(nlogn)。空间复杂度是O(1)。

JAVA代码：

public class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }
}

LeetCode解题报告：

思路三：分治算法

需要注意的是，如果左半部分得到的众数和右半部分得到的众数不相同，需要统计两个众数在整个数组出现的具体次数才能判定谁是数组中的众数。

时间复杂度是O(nlogn)。空间复杂度是O(logn)。

JAVA代码：

public class Solution {
    public int majorityElement(int[] nums) {
        return majorityElementRec(nums, 0, nums.length-1);
    }
    private int majorityElementRec(int[] nums, int left, int right) {
        if (left == right) {
            return nums[left];
        }
        int mid = (right - left)/2 + left;
        int leftResult = majorityElementRec(nums, left, mid);
        int rightResult = majorityElementRec(nums, mid + 1, right);
        if (leftResult == rightResult) {
            return leftResult;
        }
        int leftCount = countInRange(nums, leftResult, left, right);
        int rightCount = countInRange(nums, rightResult, left, right);
        return leftCount > rightCount ? leftResult : rightResult;
    }
    private int countInRange(int[] nums, int num, int left, int right) {
        int count = 0;
        for (int i = left; i <= right; i++) {
            if (nums[i] == num) {
                count++;
            }
        }
        return count;
    }
}

LeetCode解题报告：

思路四：Boyer–Moore majority vote algorithm

时间复杂度和空间复杂度均是O(n)。

JAVA代码：

public class Solution {
    public int majorityElement(int[] nums) {
        int result = nums[0];
        int count = 1;
        for (int i = 1; i < nums.length; i++) {
            if(0 == count){
                count = 1;
                result = nums[i];
            }else if(nums[i] == result){
                count++;
            }else{
                count--;
            }
        }
        return result;
    }
}

LeetCode解题报告：

思路五：位运算

int型数由32位组成，对于每一位，不是1就是0。比如对于第i位，我们可以统计nums数组中的元素，其中第i位时1的数量是ones，而第i位是0的数量是zeros。根据题意，nums数组中必然存在众数，此数的出现次数大于n / 2（向下取整）。因此ones和zeros的值不可能相等。如果ones大于zeros，那么结果的第i位必然是1，否则结果的第i位必然是0。

时间复杂度是O(n)。空间复杂度是O(1)。

JAVA代码：

public class Solution {
    public int majorityElement(int[] num) {
        int result = 0;
        for (int i = 0; i < 32; i++) {
            int ones = 0, zeros = 0;
            for (int j = 0; j < num.length; j++) {
                if ((num[j] & (1 << i)) != 0) {
                    ones++;
                }else{
                    zeros++;
                }
            }
            if (ones > zeros){
                result |= (1 << i);
            }
        }
        return result;
    }
}

LeetCode解题报告：