[Leetcode] Majority Element 众数

sihai 发布于2019-08-14 12:29 / 1828人阅读

摘要：排序法复杂度时间空间思路将数组排序，这时候数组最中间的数肯定是众数。投票法复杂度时间空间思路记录一个变量，还有一个变量，开始遍历数组。代码投票法复杂度时间空间思路上一题中，超过一半的数只可能有一个，所以我们只要投票出一个数就行了。

Majority Element I

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.

哈希表法 复杂度

时间 O(N) 空间 O(N)

思路

在遍历数组的过程中，用一个哈希表记录每个数出现过的次数，如果该次数大于一半，则说明是众数。

排序法 复杂度

时间 O(NlogN) 空间 O(1)

思路

将数组排序，这时候数组最中间的数肯定是众数。

代码

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

位操作法 复杂度

时间 O(N) 空间 O(1)

思路

假设一个数是最多只有32位的二进制数，那么我们从第一位到第32位，对每一位都计算所有数字在这一位上1的个数，如果这一位1的个数大于一半，说明众数的这一位是1，如果小于一半，说明大多数的这一位是0。

投票法 复杂度

时间 O(N) 空间 O(1)

思路

记录一个candidate变量，还有一个counter变量，开始遍历数组。如果新数和candidate一样，那么counter加上1，否则的话，如果counter不是0，则counter减去1，如果counter已经是0，则将candidate更新为这个新的数。因为每一对不一样的数都会互相消去，最后留下来的candidate就是众数。

代码

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

Majority Element II

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.

投票法 复杂度

时间 O(N) 空间 O(1)

思路

上一题中，超过一半的数只可能有一个，所以我们只要投票出一个数就行了。而这题中，超过n/3的数最多可能有两个，所以我们要记录出现最多的两个数。同样的两个candidate和对应的两个counter，如果遍历时，某个候选数和到当前数相等，则给相应计数器加1。如果两个计数器都不为0，则两个计数器都被抵消掉1。如果某个计数器为0了，则将当前数替换相应的候选数，并将计数器初始化为1。最后我们还要遍历一遍数组，确定这两个出现最多的数，是否都是众数。

代码

public class Solution {
    public List majorityElement(int[] nums) {
        List res = new ArrayList();
        if(nums.length == 0) return res;
        int c1 = 1, c2 = 0, n1 = nums[0], n2 = 0;
        for(int i = 1; i < nums.length; i++){
            // 如果和某个候选数相等，将其计数器加1
            if(nums[i] == n1){
                c1++;
            } else if(nums[i] == n2){
                c2++;
            // 如果都不相等，而且计数器都不为0，则计数器都减1
            } else if(c1 != 0 && c2 != 0){
                c1--;
                c2--;
            // 如果某个计数器为0，则更新相应的候选数
            } else {
                if(c1 == 0){
                    n1 = nums[i];
                    c1 = 1;
                } else {
                    n2 = nums[i];
                    c2 = 1;
                }
            }
        }
        c1 = 0;
        c2 = 0;
        for(int i = 0; i < nums.length; i++){
            if(nums[i] == n1) c1++;
            else if(nums[i] == n2) c2++;
        }
        if(c1 > nums.length / 3) res.add(n1);
        if(c2 > nums.length / 3) res.add(n2);
        return res;
    }
}

云服务器 GPU云服务器 Majority Element LeetCode LeetCode_String

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64506.html

LeetCode 之 JavaScript 解答第169题 —— 求众数 I（Majority El

摘要：小鹿题目算法思路摩尔投票算法题目的要求是让我们求数组中超过一半数据以上相同的元素且总是存在的。 Time：2019/4/4Title: Majority Element 1Difficulty: easyAuthor: 小鹿题目：Majority Element 1 Given an array of size n, find the majority element. The ...

hightopo 2019-08-23 16:45 评论0 收藏0
leetcode 169 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 th...

tangr206 2019-08-15 13:53 评论0 收藏0
LeetCode 之 JavaScript 解答第229题 —— 求众数 II（Majority E

摘要：继续使用摩投票算法，假设要投票，选取票数超过以上选为候选人，一个被分为三等份，也就是说最多有两位当选人。排序解决先进行一次排序快排，然后遍历数据，找出满足条件的数据。 Time：2019/4/5Title: Majority Element 2Difficulty: mediumAuthor: 小鹿问题：Majority Element 2 Given an integer ar...

BearyChat 2019-08-23 16:45 评论0 收藏0
前端 | 每天一个 LeetCode

摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...

张汉庆 2019-08-23 13:42 评论0 收藏0
leetcode讲解--169. Majority Element

摘要：当时题目改成了小明收红包，找出现次数超过一般的那个红包，要求线性时间复杂度，也就是说不能用排序排序算法最优情况是。另外这个题在上的难度是哦，好伤心啊，当初的我连这题都没想出解法，真是够年轻啊。 169. Majority Element Given an array of size n, find the majority element. The majority element i...

LiuRhoRamen 2019-07-25 11:21 评论0 收藏0