[leetcode]347. Top K Frequent Elements

347. Top K Frequent Elements

 

Given a non-empty array of integers, return the kmost frequent elements.

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2 Output: [1,2]

Example 2:

Input: nums = [1], k = 1 Output: [1]

Note:

• You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
• Your algorithm's time complexity must bebetter than O(n log n), where n is the array's size.

1 solution 

class Solution(object):
    def topKFrequent(self, nums, k):
        cnt = {}
        for n in nums:
            cnt[n] = cnt.get(n,0)+1
            
        items = cnt.items()
        items.sort(key=lambda k: k[1], reverse=True)
        return [item[0] for item in items[:k]]
 

2 solution

import random
class Solution(object):
    def findKthLargest(self, nums, k):
        pivot = random.randint(0,len(nums)-1)
        nums[0], nums[pivot] = nums[pivot], nums[0]
        bigger = [n for n in nums[1:] if n > nums[0]]
        
        if len(bigger) == k-1 :
            return nums[0]
        elif len(bigger) > k-1 :
            return self.findKthLargest(bigger, k)
        
        smaller = [n for n in nums[1:]  if n<= nums[0]]
        return self.findKthLargest(smaller, k-1-len(bigger))
        

https://leetcode.com/problems/kth-largest-element-in-an-array/