Advertisement
Iam_Sandeep

Boyer-Moore voting algorithm more than one third size of element

Sep 16th, 2021
790
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.08 KB | None | 0 0
  1. https://leetcode.com/problems/majority-element-ii/submissions/
  2. class Solution:
  3.     def majorityElement(self, nums: List[int]) -> List[int]:
  4.         if not nums:
  5.             return nums
  6.         n=len(nums)
  7.         num1=-1
  8.         num2=-1
  9.         c1=0
  10.         c2=0
  11.         for i in range(n):
  12.             if num1==nums[i]:
  13.                 c1+=1
  14.             elif num2==nums[i]:
  15.                 c2+=1
  16.             else:
  17.                 if c1==0:
  18.                     c1=1
  19.                     num1=nums[i]
  20.                 elif c2==0:
  21.                     c2=1
  22.                     num2=nums[i]
  23.                 else:
  24.                     c1=c1-1
  25.                     c2=c2-1
  26.         print(num1,num2)
  27.         f1=f2=0#actual frequencies
  28.         for i in range(n):
  29.             if nums[i]==num1:
  30.                 f1+=1
  31.             elif nums[i]==num2:
  32.                 f2+=1
  33.         print(f1,f2)
  34.         t=[]
  35.         if f1>n//3:
  36.             t.append(num1)
  37.         if f2>n//3:
  38.             t.append(num2)
  39.         return t
  40.                    
  41.    
  42.                
  43.                
  44.        
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement