[LeetCode] Majority Element

Shonim 發布于2019-08-15 15:28 / 700人閱讀

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;
    }
}

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/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