力扣(leetcode) 面試題 17.10. 主要元素 (枚舉法) (哈希表法) (中點法) (摩爾投票法)

題目在這:​​https://leetcode-cn.com/problems/find-majority-element-lcci/​​

題目分析:

一定要看清題目，題目中要求​

​請設計時間複雜度為 O(N) 、空間複雜度為 O(1) 的解決方案。​

​

思路分析:

這道題不難了解，找到出現次數最多的那個元素，并且該元素的出現次數需要大于整個數組長度的一半。

如果有兩個元素出現的次數相同，則不存在 “主要元素”

僅僅想通過leetcode，方法有很多，但是符合時間空間複雜度的，還需要想一想

法一：

我們可以直接周遊尋找出現次數最多的元素，并且幾率該元素的出現次數，然後看他是不是大于數組長度的一半。

nums = [1,2,5,9,5,9,5,5,5]
nums.sort() 
mid = nums[len(nums) // 2]
count = nums.count(mid)
if count > len(nums) // 2:
    print(mid)
else:
    print(-1)      

這時一種比較容易了解的方法，不過leetcod上直接逾時了。

法二：

仔細研究題目之後發現，如果該數組裡存在 “主要元素” ，那麼當數組排序後。中間的那個數必定是“主要元素”。

是以我們可以将數組排序，然後找到最中間的那個數，統計他的次數，最後驗證出現次數是不是大于數組長度的一半。

.sort()
 mid =nums[len(nums) // 2]
 count = nums.count(mid)
 if count > len(nums) // 2:
     print(mid)
     return mid
 else:
     print(-1)
     return -1      

注意 ：

Python3裡的sort() 排序方法，經過百度得知是一種叫 Timsort的排序方法。時間複雜度 平均為: O(nlogn)

是以上述方法已經不符合題目要求。

但是可以通過leetcod。

法三:

使用哈希表來存儲元素以及該元素出現過的次數。

最後周遊哈希表，看看那一個value大于數組長度的一般，輸出該value對應的key的值。

完整代碼：

nums = [6,5,5]
hashmap = {}
for i in nums: 
    if i in hashmap: # 元素在哈希表裡，則對應的value加1
        hashmap[i] += 1
        continue
    hashmap[i] = 1 # 元素不在哈希表裡，則加入哈希表
print(hashmap)
for key,value in hashmap.items(): # 周遊哈希表
    if value > len(nums) // 2: # 判斷是否大于數組長度的一半
        print(key)
        return key
return -1      

該方法可以通過leetcode。

時間複雜度為O(n),但外開了一個哈希表，空間複雜度不符合題目要求。

法四：

使用摩爾投票法，我們設定一個count變量。 然後周遊數組。出現相同元素的時候 count 加1，出現不同元素的時候 count減1。

如果周遊到最後 count的值 >0 則說明可能存在 “主要元素”。并不一定，因為該元素的出現次數不一定大于數組長度的一半。

設定一個res，用于記錄可能的答案。

幾個注意的點：

當投票計數器count = 0 的時候是什麼情況？

1. 顯然是一開始剛進入循環的時候。比如數組 [a,a,b]

循環開始，剛進入數組，count = 0 則記錄目前的值 ​​

​res=a​

​

2. 另外一種情況，比如數組 [a,b,b] 一開始為0 。開始周遊。

遇到a 加1，遇到b減一。此時count為0.

則記錄目前的值 ​​

​res=b​

​

是以我們得到結論，當周遊未完成的時候出現投票計數器count = 0 時。則目前可能是答案，把他記錄在res裡。

有小夥伴問:那後面出現的新的res會将前面的可能答案覆寫掉啊。

這裡完全不用擔心這個情況，因為如果出現了新的res，則說明count為0了

肯定是出現了一個新的元素，該元素出現次數為最多，才會導緻count又變成0了。

比如數組 [a,a,b,c,c,c]

顯然一開始的res記錄為a 。

count的變化：

遇到a 變為1

遇到a變為2

遇到b變為1

遇到c變為0 （此時記錄C到res中）

遇到c變為1

遇到c變為2

最後count為2 且res記錄的出現次數最多的那個值c。

是以當count = 0 。res被覆寫掉時，則說明已經有了出現次數更多的元素。

= [2,2,2,3,3,4,4]

if not nums: # 若nums為空 則直接傳回-1
    return -1

res, count = None, 0  # res記錄可能的答案，count為投票計數器

for num in nums:   # 周遊nums
    if count == 0:  # count為0的情況。可能的答案出現了
        res = num  # 記錄可能的答案
        count += 1
    else:  
        if num == res:
            count += 1
        else:
            count -= 1
if count == 0:  # 投票完成之後 count依舊為0 說明沒有數量最多的那個數。
    return -1

identify = 0

for num in nums: # 統計目前記錄的數量最多的那個數是不是超過了一半
    if num == res:
        identify += 1
        if identify > len(nums)/2:
            return res
return -1