[LeetCode] Majority Element

Shonim 发布于2019-08-15 15:28 / 622人阅读

Problem

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.

Solution

class Solution {
    public int majorityElement(int[] nums) {
        if (nums == null || nums.length == 0) return -1;
        Map map = new HashMap<>();
        for (int num: nums) {
            if (map.containsKey(num)) {
                if (map.get(num)+1 > nums.length/2) {
                    return num;
                } else {
                    map.put(num, map.get(num)+1);
                }
            } else {
                map.put(num, 1);
            }
        }
        return -1;
    }
}

update 2018-11

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

私有云专线服务 Majority Element LeetCode LeetCode_String

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

转载请注明本文地址：https://www.ucloud.cn/yun/69083.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

摘要：当时题目改成了小明收红包，找出现次数超过一般的那个红包，要求线性时间复杂度，也就是说不能用排序排序算法最优情况是。另外这个题在上的难度是哦，好伤心啊，当初的我连这题都没想出解法，真是够年轻啊。 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 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] Majority Element 众数

摘要：排序法复杂度时间空间思路将数组排序，这时候数组最中间的数肯定是众数。投票法复杂度时间空间思路记录一个变量，还有一个变量，开始遍历数组。代码投票法复杂度时间空间思路上一题中，超过一半的数只可能有一个，所以我们只要投票出一个数就行了。 Majority Element I Given an array of size n, find the majority element. The m...

sihai 2019-08-14 12:29 评论0 收藏0