当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.169.Majority Element 数组的众数/主元素

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


上一篇 LeetCode.268.Missing Number 连续数组中缺失的数

下一篇 LeetCode.066.Plus One 数组加一

阅读
评论
484
阅读预计2分钟
创建日期 2020-02-11
修改日期 2020-02-11
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论