LeetCode[169] Majority Element

int64 發布于2019-08-14 15:01 / 3252人閱讀

摘要：投票法復雜度思路設定一個和這個對應的如果一個數和這個相等，那么就將增加，否則減少的數目。

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 that the array is non-empty and the majority element always exist in the array.

投票法

復雜度
O(N),O(1)

思路
設定一個candidate,和這個candidate對應的count.如果一個數和這個candidate相等，那么就將count增加，否則減少count的數目。

代碼

public int majorityElement(int[] nums) {
    if(nums == null || nums.length == 0) return 0;
    int candidate = 0;
    int cnt = 0;
    for(int num : nums) {
        if(num == candidate) {
            cnt ++;
        }
        else if(cnt == 0) {
            candidate = num;
        }
        else {
            cnt --;
        }
    }
    return candidate;
}

GPU云服務器云服務器 Majority 169郵箱 169短信群發 Element

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/65234.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 之 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
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
Majority Vote Alogrithm（最大投票算法）及其擴展

摘要：，這是最基礎的最大投票算法。例如，和這兩個數組最后得到的分別為和，但是這并不影響答案的正確性。接下來，我們可以對這個算法做一些簡單的擴展，我們當前定義的的數量大于的元素。為當前出現的次數。這意味著當前這個數字就是這兩個等待的第三個數字。 Boyer-Moore：A Linear Time Majority Vote Alogrithm，這是最基礎的最大投票算法。原文中提到：decid...

niceforbear 2019-08-14 15:25 評論0 收藏0