How to make this leetcode method more efficient, without using count variable or perhaps another way-CodePudding

This is for leetcode problem: https://leetcode.com/problems/majority-element

There is something wrong with the way I create solutions, and not sure how to stop doing it. Basically the problem is I always create a count variable. Here is it called greatest_count. For the if statement, I create a conditional, which I think is fine, but I feel like I don't need the additional greatest_count variable here but not sure a better way to write it. I always seem to think I need to count it and check it against the previous counts. Do I need this? How can I write this without needing the count variable? or without using the greatest unique? Any ways to optimize this would be great to know.

Problem area:

if unique_count > greatest_count:
   greatest_count = unique_count
   greatest_unique = i

Here is the full code:

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

Thank you

CodePudding user response：

In order to get this to work in O(n) time and O(1) space, you would need a different approach. For example, find the majority bit for each of the 32 bits of the numbers and build the answer from the collected bits that are present in more than half the numbers:

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

This is O(n) (linear) time because it runs through the list a fixed number of times. It is O(1) space because it does not use memory proportionally to the size of the list.