leetcode講解--169. Majority Element

LiuRhoRamen 發(fā)布于2019-07-25 11:21 / 2293人閱讀

摘要：當時題目改成了小明收紅包，找出現(xiàn)次數(shù)超過一般的那個紅包，要求線性時間復雜度，也就是說不能用排序排序算法最優(yōu)情況是。另外這個題在上的難度是哦，好傷心啊，當初的我連這題都沒想出解法，真是夠年輕啊。

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.

題目地址

唉，看到這題就想起了，當年，青蔥歲月，菜雞的我做阿里的筆試題，對的，就是這題。當時題目改成了小明收紅包，找出現(xiàn)次數(shù)超過一般的那個紅包，要求線性時間復雜度，也就是說不能用排序（排序算法最優(yōu)情況是：O(nlogn)）。

出現(xiàn)次數(shù)超過一半的那個數(shù)，我們怎么在O(n)時間復雜度內把它揪出來，我教你：大浪淘沙法，是金子總會發(fā)光法，我要打十個法（意思就是，這一個數(shù)就能干翻全場剩下的所有數(shù)，是不是？因為它超過一半?。Ｎ覀儊硐胂笠幌拢何覀儽闅v這個數(shù)組的時候，定義一個count用來計數(shù)，這個超過一半的數(shù)，它遇到自己就給count加1，遇到不是自己的數(shù)，就給count減1，最后會怎樣呢，count肯定大于0吶，因為這個數(shù)的個數(shù)超過一半。好，進一步的，我們先隨便找個數(shù)當這個老大（個數(shù)超過一半），如果它的個數(shù)不超過一半，就會在相消中時count為0，那么就把它換掉，最后剩下的那個就是，個數(shù)超過一半的那個數(shù)了。

代碼如下：

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        count = 1
        n = nums[0]
        for x in range(1, len(nums)):
            if count == 0:
                n = nums[x]
                count += 1
            else:
                if nums[x] == n:
                    count += 1
                else:
                    count -= 1
        return n

超過一半吶，多么重的一條信息，稍微想想就知道，用相消法都能消出那個數(shù)，跟那個用異或消出只出現(xiàn)一次的數(shù)（其它的數(shù)都是成對的，就是都恰好有兩個）是不是異曲同工吶，嗯還是扯得有點遠。

另外這個題在leetcode上的難度是easy哦，好傷心啊，當初的我連這題都沒想出解法，真是夠年輕啊。

云服務器 GPU云服務器 Majority 169郵箱 169短信群發(fā) Element

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

轉載請注明本文地址：http://systransis.cn/yun/38353.html

LeetCode[169] Majority Element

摘要：投票法復雜度思路設定一個和這個對應的如果一個數(shù)和這個相等，那么就將增加，否則減少的數(shù)目。 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題 —— 求眾數(shù) I（Majority El

摘要：小鹿題目算法思路摩爾投票算法題目的要求是讓我們求數(shù)組中超過一半數(shù)據以上相同的元素且總是存在的。 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

摘要：題目鏈接題目分析給定一個數(shù)組，返回其中出現(xiàn)次數(shù)超過一半的元素。思路用函數(shù)計算元素出現(xiàn)次數(shù)，用逆序排序結果，輸出第一個即可。最終代碼若覺得本文章對你有用，歡迎用愛發(fā)電資助。 D83 169. Majority Element 題目鏈接 169. Majority Element 題目分析給定一個數(shù)組，返回其中出現(xiàn)次數(shù)超過一半的元素。思路用array_count_values函數(shù)計算...

yagami 2019-07-01 13:57 評論0 收藏0
leetcode 169 Majority Element

摘要：因為眾數(shù)出現(xiàn)的次數(shù)必定大于，所以我們只要取第個位置上的元素，這個元素一定為我們要找的眾數(shù)。題目詳情 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（最大投票算法）及其擴展

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

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