這是 leetcode 問題：https ://leetcode.com/problems/majority-element
我創建解決方案的方式有問題，不知道如何停止這樣做。基本上問題是我總是創建一個計數變數。它被稱為 best_count。對于 if 陳述句，我創建了一個條件，我認為這很好，但我覺得這里不需要額外的 best_count 變數，但不確定是否有更好的撰寫方式。我似乎總是認為我需要計算它并對照以前的計數進行檢查。我需要這個嗎？我怎樣才能在不需要計數變數的情況下寫這個？或不使用最大的唯一性？任何優化這一點的方法都會很高興知道。
問題區域：
if unique_count > greatest_count:
greatest_count = unique_count
greatest_unique = i
這是完整的代碼：
class Solution:
def majorityElement(self, nums):
unique_nums = set(nums)
greatest_unique = 0
greatest_count = 0
for i in unique_nums:
unique_count = nums.count(i)
if unique_count > greatest_count:
greatest_count = unique_count
greatest_unique = i
return greatest_unique
謝謝
uj5u.com熱心網友回復：
為了讓它在 O(n) 時間和 O(1) 空間中作業，您需要一種不同的方法。例如，為數字的 32 位中的每一個找到多數位，并根據超過一半數字中存在的收集位構建答案：
def majorityElement(nums):
m = 0
for b in range(32): # go through all 32 bits
c = sum(n&(2**b)!=0 for n in nums) # count numbers with bit b set
if c>len(nums)//2: m |= 2**b # more than half, keep that bit
return m if m<2**31 else m-2**32 # turn Python's int to 32 bit signed
majorityElement([3,2,3]) # 3
majorityElement([-3,-3,1,1,1,-3,-3]) # -3
這是 O(n)（線性）時間，因為它在串列中運行固定次數。它是 O(1) 空間，因為它沒有與串列的大小成比例地使用記憶體。
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/329731.html
下一篇：使用可格式化包自動自定義表格