如何使这个leetcode方法更有效，不使用计数变量或其他方式?

Question

这是针对leetcode问题:https://leetcode.com/problems/majority-element

我创造解决方案的方式有问题，不知道如何停止这样做。基本上问题是我总是创建一个count变量。这里它叫做greatest_count。对于if语句，我创建了一个条件，我认为这很好，但我觉得我不需要这里额外的greatest_count变量，但不确定更好的编写方式。我似乎总是认为我需要数一数，并与之前的数进行核对。我需要这个吗?如何在不需要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

谢谢

Answer 1

为了让它在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)空间，因为它不使用与列表大小成比例的内存。