169、多数元素

leetcode

Created At : 2020-07-26 00:19

Count:700 Views 👀 :

Comment:

169、多数元素
1. 示例 1:
2. 示例 2:
题解

169、多数元素

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

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

示例 1:

输入: [3,2,3]
输出: 3

示例 2:

输入: [2,2,1,1,1,2,2]
输出: 2

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

题解

1、利用hash统计

class Solution {
    public int majorityElement(int[] nums) {
        int res = 0;
        if (nums.length <= 2) return nums[0];
        // 数字统计
        Map<Integer,Integer> numCount = new HashMap<>();
        for (int num : nums) {
            if (numCount.containsKey(num)){
                numCount.put(num,numCount.get(num)+1);
                if (numCount.get(num) > nums.length/2) {
                    res = num;
                    break;
                }
            }else{
                numCount.put(num,1);
            }
        }
        return res;
    }
}

2、排序后返回中间元素

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

3、投票法

对数组进行遍历，对数字进行投票。
当某个数字的投票变为0时，更换为新的数字。

class Solution {
    public int majorityElement(int[] nums) {
        int count = 0;
        int tmp = nums[0];
        for (int num : nums) {
            if (count == 0){
                tmp = num;
            }
            count += (tmp == num) ? 1:-1;
        }
        return tmp;
    }
}

4、随机法

随机选择数组中的元素，判断该元素是否为众数，是则返回。

否则继续上述操作。

class Solution {
    private int randRange(Random rand, int min, int max) {
        return rand.nextInt(max - min) + min;
    }

    private int countOccurences(int[] nums, int num) {
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == num) {
                count++;
            }
        }
        return count;
    }

    public int majorityElement(int[] nums) {
        Random rand = new Random();

        int majorityCount = nums.length/2;

        while (true) {
            int candidate = nums[randRange(rand, 0, nums.length)];
            if (countOccurences(nums, candidate) > majorityCount) {
                return candidate;
            }
        }
    }
}

// 作者：LeetCode-Solution
// 链接：https://leetcode-cn.com/problems/majority-element/solution/duo-shu-yuan-su-by-leetcode-solution/

5、分治法

利用部分数组也是包含目标众数的原理。
算法：

二分递归
- 获得左众数
- 获得右众数
- 相等，直接返回
进一步统计左右众数的数量
- 返回数量较大的那个
直至递归全部回溯。

class Solution {
    private int countInRange(int[] nums, int num, int lo, int hi) {
        int count = 0;
        for (int i = lo; i <= hi; i++) {
            if (nums[i] == num) {
                count++;
            }
        }
        return count;
    }

    private int majorityElementRec(int[] nums, int lo, int hi) {
        // base case; the only element in an array of size 1 is the majority
        // element.
        if (lo == hi) {
            return nums[lo];
        }

        // recurse on left and right halves of this slice.
        int mid = (hi-lo)/2 + lo;
        int left = majorityElementRec(nums, lo, mid);
        int right = majorityElementRec(nums, mid+1, hi);

        // if the two halves agree on the majority element, return it.
        if (left == right) {
            return left;
        }

        // otherwise, count each element and return the "winner".
        int leftCount = countInRange(nums, left, lo, hi);
        int rightCount = countInRange(nums, right, lo, hi);

        return leftCount > rightCount ? left : right;
    }

    public int majorityElement(int[] nums) {
        return majorityElementRec(nums, 0, nums.length-1);
    }
}

// 作者：LeetCode-Solution
// 链接：https://leetcode-cn.com/problems/majority-element/solution/duo-shu-yuan-su-by-leetcode-solution/

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com