https://leetcode.com/problems/top-k-frequent-elements/

kMostFrequest.py

import random
from collections import defaultdict

# quickSelect
# n = len(list)
# k = discintElementsInList
# O(n + k)
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        
        counts = defaultdict(int)
        for n in nums:
            counts[n]+=1
        
        countList = [(count, num) for num, count in counts.items()]
        
        l, r = 0, len(countList)-1
        while(l <= r):
            mid = self.partition(countList, l, r)
            if mid < k-1:
                l = mid+1
            elif mid > k-1:
                r - mid-1
            else:
                return [num for count, num in countList[0:mid+1]]
        
    def partition(self, nums, l, r):
        pivotIndex = random.randint(l, r)
        pivot, rightEnd = nums[pivotIndex], r
        nums[pivotIndex], nums[r] = nums[r], nums[pivotIndex]
        r-=1
        while(l <= r):
            if(nums[l][0] >= pivot[0]):
                l+=1
            else:
                nums[l], nums[r] = nums[r], nums[l]
                r-=1
        nums[rightEnd], nums[l] = nums[l], nums[rightEnd]
        return l