LeetCode.169.Majority Element 数组的众数/主元素

题目描述

169 Majority Element
https://leetcode-cn.com/problems/majority-element/

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Example 1:

Input: [3,2,3]
Output: 3

Example 2:

Input: [2,2,1,1,1,2,2]
Output: 2

---

解题过程

求数组中出现次数超过一半的数，即数组的众数，非常经典的题。
最直观的想法就是排序后取 下标 n/2 的元素，时间复杂度是 O(nlogn)。
或者用一个map统计每个元素出现的次数，实际复杂度 O(n)，空间复杂度 O(n)

摩尔投票法

题解中有一个很厉害的O(n)方法，叫 摩尔投票算法，
1980 年由 Boyer 和 Moore 两个人提出来的算法，英文是 Boyer-Moore Majority Vote Algorithm
思想是：看做好几个不同军队抢夺一个高地，他们一对一消耗因为有个军队超过了n/2，经过消耗后，他还有人活着。
从第一个数开始count=1，遇到相同的就加1，遇到不同的就减1，减到0就重新换个数开始计数，最后剩下的数就是众数。

快速排序应用

或者 快速排序的应用 ，由于每次 partition 后枢轴的位置是固定，这个方法也适用于求数组中第k大(小)的元素，但实际证明性能很差，只打败了5%。

private static class SolutionV2020 {
    public int majorityElement(int[] nums) {
        int mid = (nums.length) / 2;
        int partition = partition(nums, 0, nums.length - 1);
        while (partition != mid) {
            if (partition < mid) {
                partition = partition(nums, partition + 1, nums.length - 1);
            } else {
                partition = partition(nums, 0, partition -1);
            }
        }
        int major = nums[partition];
        return major;
    }

    private int partition(int[] nums, int low, int high) {
        int pivot = nums[low];
        while (low < high) {
            for(; nums[high] >= pivot && low < high; high--) {
            }
            nums[low] = nums[high];
            for(; nums[low] <= pivot && low < high; low++) {
            }
            nums[high] = nums[low];
        }
        // 枢轴归位
        nums[low] = pivot;
        return low;
    }
}

---

GitHub代码

algorithms/leetcode/leetcode/_169_MajorityElement.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_169_MajorityElement.java

---