#solution involving minHeap #Strategy: #1) Take out the smallest number from the heap, and #2) Insert the larger number into the heap. #3) repeat #This will ensure that we always have ‘K’ largest numbers in the heap. The most efficient way to repeatedly find the smallest number among a set of numbers will be to use a min-heap. #Big O n log k. Space: O (k) from heapq import * #this is a heap library. look at relevant functions: https://docs.python.org/3/library/heapq.html def find_k_largest_numbers(nums, k): minHeap = [] # put first 'K' numbers in the min heap for i in range(k): heappush(minHeap, nums[i]) # go through the remaining numbers of the array, if the number from the array is bigger than the # top(smallest) number of the min-heap, remove the top number from heap and add the number from array for i in range(k, len(nums)): if nums[i] > minHeap[0]: #heapop removes smallest element in heap heappop(minHeap) heappush(minHeap, nums[i]) # the heap has the top 'K' numbers return minHeap #brute force approach has big O of n log N def find_k_largest_numbers(nums, k): result = [] nums.sort() nums_length_index = len(nums) - 1 - k for i in range(nums_length_index + 1, len(nums)): result.append(nums[i]) return result find_k_largest_numbers([3, 1, 5, 12, 2, 12], 3) # will result in [5, 12, 12] #if you dont want duplicates you can do the following: def find_k_largest_numbers(nums, k): result = [] nums.sort() nums_set = set(nums) nums_length_index = len(nums_set) - 1 - k for i in range(nums_length_index + 1, len(nums_set)): result.append(nums[i]) return result
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter