中文字幕av专区_日韩电影在线播放_精品国产精品久久一区免费式_av在线免费观看网站

溫馨提示×

溫馨提示×

您好,登錄后才能下訂單哦!

密碼登錄×
登錄注冊×
其他方式登錄
點擊 登錄注冊 即表示同意《億速云用戶服務條款》

LeetCode如何找出數組中出現次數超過一半的數字

發布時間:2021-12-15 14:18:27 來源:億速云 閱讀:149 作者:小新 欄目:大數據

這篇文章主要為大家展示了“LeetCode如何找出數組中出現次數超過一半的數字”,內容簡而易懂,條理清晰,希望能夠幫助大家解決疑惑,下面讓小編帶領大家一起研究并學習一下“LeetCode如何找出數組中出現次數超過一半的數字”這篇文章吧。

題目描述

數組中有一個數字出現的次數超過數組長度的一半,請找出這個數字。

你可以假設數組是非空的,并且給定的數組總是存在多數元素。

1 <= 數組長度 <= 50000

       

題目樣例

       

示例

輸入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 輸出: 2

       

題目思考

  1. 如何不使用額外空間?
  2. 如果題目不保證一定存在多數元素又該怎么辦?
       

解決方案

       
思路
  • 一個最簡單的思路是用一個計數字典存每個數字的出現次數, 找最大的那個即可, 但這需要額外的空間, 不是面試官心目中的理想答案
  • 重新分析題目, 某個數字出現超過一半, 那意味著其他數字的數目之和都小于它, 如果我們將這些 不同數字進行兩兩抵消, 那么最后剩余的那個數字一定是超過一半的那個數字, 這就引出了下面的思路:
    1. 維護一個當前候選者, 以及當前它的計數, 初始化就是數組頭一個數字, 計數為 1
    2. 從第二個數字開始遍歷數組, 如果當前數字等于候選者, 那么計數值加 1, 否則就減 1 表示抵消了一個數字
    3. 如果此時計數小于 0 的話, 就說明之前的候選者這個時候要被淘汰了, 因為它已經被抵消光了. 所以就重新選擇當前的數字作為新的候選者, 同時重置計數值為 1.
    4. 這樣最后剩余的那個候選者一定是最終結果, 因為此題的前提是一定存在這樣的數字
  • 當然, 如果題目不保證一定存在多數元素, 那么我們在得到最終候選者之后, 需要重新遍歷一遍數組并累加其計數, 確保其計數超過一半, 不然的話就說明整個數組沒有多數元素. 例如數組 [1,2,3], 利用此方法得到的最終候選者為 3, 但它并不是多數元素, 只是恰好最后一個被選出來的候選者而已.
       
復雜度
  • 時間復雜度 O(N)
    • 只需要遍歷數組一遍
  • 空間復雜度 O(1)
    • 只使用了幾個變量
       
代碼
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        # 初始化候選者和計數
        res = nums[0]
        cnt = 1
        for x in nums[1:]:
            if x == res:
                # 當前元素等于候選者, 計數值+1
                cnt += 1
            else:
                # 否則計數值-1
                cnt -= 1
                if cnt < 0:
                    # 如果計數值小于0的話, 就說明之前保存的候選者現在被淘汰了, 將當前元素變為新的候選者, 并重置計數值為1
                    res = x
                    cnt = 1
        return res

以上是“LeetCode如何找出數組中出現次數超過一半的數字”這篇文章的所有內容,感謝各位的閱讀!相信大家都有了一定的了解,希望分享的內容對大家有所幫助,如果還想學習更多知識,歡迎關注億速云行業資訊頻道!

向AI問一下細節

免責聲明:本站發布的內容(圖片、視頻和文字)以原創、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯系站長郵箱:is@yisu.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。

AI

伊宁县| 时尚| 福清市| 土默特右旗| 永川市| 静海县| 察雅县| 陆河县| 朔州市| 错那县| 闵行区| 霍城县| 南阳市| 秦安县| 横峰县| 石渠县| 额敏县| 德清县| 修文县| 洛南县| 深泽县| 成安县| 巴彦县| 宝清县| 阿城市| 仙游县| 葫芦岛市| 永泰县| 武城县| 湘乡市| 隆安县| 南乐县| 海伦市| 如皋市| 镶黄旗| 镇宁| 华阴市| 莒南县| 平遥县| 清镇市| 昔阳县|