leetcode 169 Majority Element

tangr206 发布于2019-08-15 13:53 / 2879人阅读

摘要：因为众数出现的次数必定大于，所以我们只要取第个位置上的元素，这个元素一定为我们要找的众数。

题目详情

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.

输入一个大小为n的数组，整个数组里面将会含有一个众数，即这个元素出现的次数大于n/2，我们需要找到并返回这个众数

思路

这道题也是一道关于数组的重复元素的问题

首先我想到的办法是，使用HashMap实现，key是元素的值，value则是这个元素在当前出现的次数，一旦这个次数大于n/2，我们就可以停止我们的遍历

但实际上，还有一种更简单的方法。因为众数出现的次数必定大于n／2，所以我们只要取第n/2个位置上的元素，这个元素一定为我们要找的众数。

感谢@SegmentWarrior提供的解法三，不需要建立hashmap所产生的额外空间，同时时间复杂度为O(n)

解法一 HashMap

    //HashMap实现 时间复杂度O(n)
    public int majorityElement(int[] nums) {
        HashMap count = new HashMap();
        int length = nums.length;
        if(length<=1){
            return nums[0];
        }
        for(int i=0;i length/2){
                    return nums[i];
                }
            }else{
                count.put(nums[i], 1);
            }

        }
        
        return -1;
    }

解法二直接取n/2位置元素

    //思想：对于一个排序好的数组，第n/2的位置的元素一定是存在的这个众数
    public int majorityElement(int[] nums) {
        
        Arrays.sort(nums);
        return nums[nums.length/2];
    }

解法三对出现次数计数

    public int majorityElement(int[] nums) {
        int res = nums[0];
        int count = 1;
        
        for(int i=1;i1) count --;
            else res = nums[i];
        }
        return res;
    }

云服务器 GPU云服务器 Majority 169邮箱 169短信群发 Element

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

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

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
LeetCode[169] Majority Element

摘要：投票法复杂度思路设定一个和这个对应的如果一个数和这个相等，那么就将增加，否则减少的数目。 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...

int64 2019-08-14 15:01 评论0 收藏0
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 PHP题解--D83 169. Majority Element

摘要：题目链接题目分析给定一个数组，返回其中出现次数超过一半的元素。思路用函数计算元素出现次数，用逆序排序结果，输出第一个即可。最终代码若觉得本文章对你有用，欢迎用爱发电资助。 D83 169. Majority Element 题目链接 169. Majority Element 题目分析给定一个数组，返回其中出现次数超过一半的元素。思路用array_count_values函数计算...

yagami 2019-07-01 13:57 评论0 收藏0
Majority Vote Alogrithm（最大投票算法）及其扩展

摘要：，这是最基础的最大投票算法。例如，和这两个数组最后得到的分别为和，但是这并不影响答案的正确性。接下来，我们可以对这个算法做一些简单的扩展，我们当前定义的的数量大于的元素。为当前出现的次数。这意味着当前这个数字就是这两个等待的第三个数字。 Boyer-Moore：A Linear Time Majority Vote Alogrithm，这是最基础的最大投票算法。原文中提到：decid...

niceforbear 2019-08-14 15:25 评论0 收藏0