In Doraland, people have unique Identity Numbers called D-id. Doraemon owns the most popular gadget shop in Doraland. Since his gadgets are in high demand and he has only K gadgets left he has decided to sell his gadgets to his most frequent customers only. N customers visit his shop and D-id of each customer is given in an array array[ ]. In case two or more people have visited his shop the same number of time he gives priority to the customer with higher D-id. Find the D-ids of people he sells his K gadgets to.
Example 1:
Input:
N = 6
array[] = {1, 1, 1, 2, 2, 3}
K = 2
Output: 
1 2
Explanation: 
Customers with D-id 1 and 2 are most 
frequent.
Example 2:
Input:
N = 8
array[] = {1, 1, 2, 2, 3, 3, 3, 4}
K = 2
Output: 
3 2
Explanation: People with D-id 1 and 2 have 
visited shop 2 times Therefore, in this 
case, the answer includes the D-id 2 as 2 > 1.
Your Task:
You don't need to read input or print anything. Complete the function TopK() which takes array[ ] and integer K as input parameters and returns an array containing D-id of customers he has decided to sell his gadgets to.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^{5}
1 ≤ D-id ≤ 10^{4}

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Data structures

Starter code: #User function Template for python3



class Solution:

    def TopK(self, array, k):

        # code here





Solutions:
import heapq
from collections import defaultdict

class Solution:

	def TopK(self, array, k):
		hmap = defaultdict(int)
		ans = []
		for i in range(0, len(array)):
			if array[i] not in hmap:
				hmap[array[i]] = 1
			else:
				hmap[array[i]] += 1
		maxheap = []
		for (key, value) in hmap.items():
			heapq.heappush(maxheap, (-value, -key))
		while k > 0:
			ele = heapq.heappop(maxheap)
			ans.append(ele[1] * -1)
			k -= 1
		return ans


from collections import Counter

class Solution:

	def TopK(self, array, k):
		d = {}
		x = []
		out = []
		for i in array:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		for i in d:
			x.append([i, d[i]])
		x.sort(reverse=True, key=lambda x: (x[1], x[0]))
		for i in range(k):
			out.append(x[i][0])
		return out


import heapq

class Solution:

	def TopK(self, array, k):
		d = {}
		for i in array:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		heap = []
		res = []
		for (i, j) in d.items():
			heapq.heappush(heap, (-j, -i))
		while k > 0:
			res.append(heapq.heappop(heap)[1] * -1)
			k -= 1
		return res


class Solution:

	def TopK(self, array, k):
		freq = {}
		for i in array:
			if i not in freq:
				freq[i] = 0
			freq[i] += 1
		lis = list(freq.items())
		lis.sort(key=lambda x: (x[1], x[0]), reverse=True)
		ans = []
		for i in range(k):
			ans.append(lis[i][0])
		return ans


import heapq

class Solution:

	def TopK(self, array, k):
		d = {}
		for i in array:
			d[i] = 1 + d.get(i, 0)
		heap = []
		for key in d:
			heapq.heappush(heap, [d[key], key])
			if len(heap) > k:
				heapq.heappop(heap)
		heapq._heapify_max(heap)
		d.clear()
		res = []
		while heap:
			p = heapq._heappop_max(heap)
			res.append(p[1])
		return res


class Solution:

	def TopK(self, array, k):
		array.sort(key=lambda x: x, reverse=True)
		m = []
		count = 1
		for i in range(1, len(array)):
			if array[i] == array[i - 1]:
				count += 1
			else:
				m.append([array[i - 1], count])
				count = 1
		m.append([array[-1], count])
		m.sort(key=lambda x: x[1], reverse=True)
		ans = []
		for i in range(k):
			ans.append(m[i][0])
		return ans


from collections import Counter
from heapq import *

class Solution:

	def TopK(self, array, k):
		d = {}
		for i in array:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		d1 = sorted(d.keys(), key=lambda x: d[x], reverse=True)
		d2 = {}
		for i in d1:
			if d[i] not in d2:
				d2[d[i]] = [i]
			else:
				d2[d[i]].append(i)
		d3 = sorted(d2.keys(), reverse=True)
		l = []
		for i in d3:
			if len(d2[i]) > 1:
				d2[i].sort(reverse=True)
				l += d2[i]
			else:
				l += d2[i]
		return l[:k]


from heapq import *

class Solution:

	def TopK(self, array, k):
		m = {}
		for i in range(0, len(array)):
			if -array[i] not in m:
				m[-array[i]] = -1
			else:
				m[-array[i]] -= 1
		h = list(zip(m.values(), m.keys()))
		heapify(h)
		ids = []
		for _ in range(k):
			ids.append(-1 * heappop(h)[1])
		return ids


from collections import Counter

class Solution:

	def TopK(self, array, k):
		items = list(Counter(array).items())
		items.sort(reverse=True)
		items.sort(key=lambda x: x[1], reverse=True)
		return [item[0] for item in items][:k]


from collections import Counter
from heapq import *

class Solution:

	def TopK(self, array, k):
		d = {}
		for i in array:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		maxheap = []
		lst = []
		for (i, j) in d.items():
			heappush(maxheap, (-j, -i))
		while k > 0:
			lst.append(heappop(maxheap)[1] * -1)
			k -= 1
		return lst


import heapq as hp

class Solution:

	def TopK(self, array, k):
		d = {}
		ans = []
		for i in array:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		lp = []
		for i in d:
			lp.append((d[i], i))
		lp.sort(key=lambda x: (-x[0], -x[1]))
		for i in range(k):
			ans.append(lp[i][1])
		return ans


class Solution:

	def TopK(self, a, k):
		d = {}
		for i in a:
			if i in d.keys():
				d[i] += 1
			else:
				d[i] = 1
		l = []
		for j in d.keys():
			l.append([d[j], j])
		l.sort()
		l = l[::-1]
		t = []
		for i in range(k):
			t.append(l[i][1])
		return t


class Solution:

	def TopK(self, array, k):
		m = {}
		for i in array:
			if i in m:
				m[i] += 1
			else:
				m[i] = 1
		b = []
		for i in m:
			b.append([m[i], i])
		b.sort(key=lambda x: (-x[0], -x[1]))
		return b[:k]


import heapq

class Solution:

	def TopK(self, array, k):
		count = {}
		for element in array:
			if element in count:
				count[element] += 1
			else:
				count[element] = 1
		heap = []
		for (i, j) in count.items():
			heapq.heappush(heap, (-j, -i))
		ans = []
		while k:
			ans.append(heapq.heappop(heap)[1] * -1)
			k -= 1
		return ans


class Solution:

	def TopK(self, array, k):
		d = {}
		for i in array:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		x = []
		for i in d:
			a = [d[i], i]
			x.append(a)
		x.sort(reverse=True)
		ans = []
		for i in range(k):
			ans.append(x[i][1])
		return ans


from collections import Counter

class Solution:

	def TopK(self, array, K):
		d = Counter(array)
		a = []
		b = []
		for i in d:
			a.append(d[i])
			b.append(i)
		z = sorted(list(zip(a, b)), reverse=True)
		lst = []
		for (x, y) in z:
			lst.append(y)
			K -= 1
			if K == 0:
				break
		return lst


import heapq as h

class Solution:

	def TopK(self, array, k):
		dict = {}
		for i in array:
			dict[i] = dict.get(i, 0) + 1
		heapmax = [[-cnt, -iD] for (iD, cnt) in dict.items()]
		h.heapify(heapmax)
		i = 0
		lst = []
		while i < k:
			(cnt, iD) = h.heappop(heapmax)
			lst.append(iD * -1)
			i += 1
		return lst
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		array = [int(x) for x in input().strip().split()]
		k = int(input())
		obj = Solution()
		res = obj.TopK(array, k)
		for each in res:
			print(each, end=' ')
		print()


import heapq as h

class Solution:

	def TopK(self, array, k):
		ids = {}
		for i in array:
			if i in ids.keys():
				ids[i] += 1
			else:
				ids[i] = 1
		heap = []
		res = []
		for i in ids.keys():
			h.heappush(heap, (-ids[i], -i))
		while k > 0 and heap:
			res.append(h.heappop(heap)[1] * -1)
			k -= 1
		return res
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		array = [int(x) for x in input().strip().split()]
		k = int(input())
		obj = Solution()
		res = obj.TopK(array, k)
		for each in res:
			print(each, end=' ')
		print()


from heapq import *

class Solution:

	def TopK(self, array, k):
		ans = []
		gg = {}
		for i in array:
			gg[i] = gg.get(i, 0) + 1
		for i in gg:
			heappush(ans, (-gg[i], -i))
		res = []
		for i in range(k):
			a = heappop(ans)
			res.append(-a[1])
		return res
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		array = [int(x) for x in input().strip().split()]
		k = int(input())
		obj = Solution()
		res = obj.TopK(array, k)
		for each in res:
			print(each, end=' ')
		print()


import heapq

class Solution:

	def TopK(self, array, k):
		d = {}
		for num in array:
			if num in d:
				d[num] += 1
			else:
				d[num] = 1
		heap = []
		res = []
		for (i, j) in d.items():
			heapq.heappush(heap, (-j, -i))
		while k > 0:
			res.append(heapq.heappop(heap)[1] * -1)
			k = k - 1
		return res
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		array = [int(x) for x in input().strip().split()]
		k = int(input())
		obj = Solution()
		res = obj.TopK(array, k)
		for each in res:
			print(each, end=' ')
		print()


import heapq

class Solution:

	def TopK(self, array, k):
		frequency = dict()
		for num in array:
			if num in frequency:
				frequency[num] += 1
			else:
				frequency[num] = 1
		pair = []
		for key in frequency.keys():
			pair.append((frequency[key] * -1, key * -1))
		heapq.heapify(pair)
		res = []
		while k:
			(_, dId) = heapq.heappop(pair)
			res.append(dId * -1)
			k -= 1
		return res


class Solution:

	def TopK(self, array, k):
		Map = {}
		for i in array:
			if i not in Map:
				Map[i] = 1
			else:
				Map[i] = Map[i] + 1
		List = sorted([(val, key) for (key, val) in Map.items()], reverse=True)
		ans = []
		for i in range(k):
			ans.append(List[i][1])
		return ans


import heapq

class Solution:

	def TopK(self, array, k):
		D_id = []
		map1 = dict()
		for i in array:
			if i not in map1:
				map1[i] = 0
			map1[i] += 1
		list1 = [[-val, -key] for (key, val) in map1.items()]
		heapq.heapify(list1)
		K = k
		while len(list1) != 0 and K > 0:
			val = heapq.heappop(list1)
			D_id.append(val)
			while len(list1) != 0 and val[0] == list1[0][0]:
				val1 = heapq.heappop(list1)
				D_id.append(val1)
			K -= 1
		D_id = [-i[1] for i in D_id]
		res = D_id[:k]
		return res


from heapq import *

class Solution:

	def TopK(self, array, k):
		min_heap = []
		d = {}
		for i in array:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		for i in d:
			heappush(min_heap, [d[i], i])
			if len(min_heap) > k:
				heappop(min_heap)
		t = []
		for i in range(k):
			(a, b) = heappop(min_heap)
			t.append(b)
		return t[::-1]


import heapq

class Solution:

	def TopK(self, array, k):
		dict = {}
		for i in array:
			if i in dict:
				dict[i] += 1
			else:
				dict[i] = 1
		l = [[-1 * value, -1 * key] for (key, value) in dict.items()]
		heapq.heapify(l)
		answer = []
		for j in range(k):
			answer.append(-1 * heapq.heappop(l)[1])
		return answer


from collections import Counter
import heapq

class Solution:

	def TopK(self, array, k):
		mp = Counter(array)
		l = []
		for i in mp.keys():
			heapq.heappush(l, (-mp[i], -i))
		i = 0
		l1 = []
		while i < k:
			l1.append(heapq.heappop(l)[1] * -1)
			i += 1
		return l1


class Solution:

	def TopK(self, array, k):
		counts = dict()
		for i in array:
			counts[i] = counts.get(i, 0) + 1
		nl = sorted([(v, k) for (k, v) in counts.items()], reverse=True)
		nnl = list()
		for i in range(k):
			nnl.append(nl[i][1])
		return nnl


from collections import defaultdict
from queue import PriorityQueue as pq

class Solution:

	def TopK(self, array, k):
		hashmap = dict()
		for i in array:
			try:
				hashmap[i] += 1
			except:
				hashmap[i] = 1
		arr = list(set(array))
		arr.sort(reverse=True)
		arr.sort(key=lambda i: hashmap[i], reverse=True)
		return arr[:k]


from collections import defaultdict as df
import heapq as h

class Solution:

	def TopK(self, array, k):
		d = df(int)
		for i in array:
			d[i] += 1
		l = [(d[i] * -1, i * -1) for i in d]
		h.heapify(l)
		return [h.heappop(l)[1] * -1 for i in range(k)]


from collections import Counter
import heapq as h

class Solution:

	def TopK(self, a, k):
		x = {}
		for i in a:
			x[i] = x.get(i, 0) + 1
		fr = {}
		for i in x:
			try:
				fr[x[i]]
			except:
				fr[x[i]] = []
			h.heappush(fr[x[i]], -i)
		hp = [-i for i in x.values()]
		h.heapify(hp)
		x = []
		for i in range(k):
			x.append(-h.heappop(fr[-h.heappop(hp)]))
		return x


class Solution:

	def TopK(self, array, k):
		cnt = dict()
		for i in array:
			cnt[i] = cnt.get(i, 0) + 1
		val = sorted([(i, j) for (j, i) in cnt.items()], reverse=True)
		result = []
		for i in range(k):
			result.append(val[i][1])
		return result


from collections import Counter
from heapq import heappush, heappop, heapify

class Solution:

	def TopK(self, array, k):
		d = Counter(array)
		h = sorted([(v, k) for (k, v) in d.items()], reverse=True)
		ans = []
		for i in range(k):
			ans.append(h[i][1])
		return ans


import heapq

class Solution:

	def TopK(self, array, k):
		minHeap = []
		heapq.heapify(minHeap)
		freq = dict()
		for element in array:
			freq[element] = freq.get(element, 0) + 1
		for (key, value) in freq.items():
			if len(minHeap) < k:
				heapq.heappush(minHeap, (value, key))
			else:
				(minValue, minKey) = (minHeap[0][0], minHeap[0][1])
				if value > minValue:
					heapq.heapreplace(minHeap, (value, key))
				elif value == minValue:
					if key > minKey:
						heapq.heapreplace(minHeap, (value, key))
		ans = []
		while minHeap:
			minValue = heapq.heappop(minHeap)[1]
			ans.append(minValue)
		ans = ans[::-1]
		return ans


class Solution:

	def TopK(self, array, k):
		freq = {}
		for i in range(len(array)):
			if array[i] not in freq:
				freq[array[i]] = 1
			else:
				freq[array[i]] += 1
		SortedFreqs = sorted([(v, k) for (k, v) in freq.items()], reverse=True)
		Keys = []
		for i in range(k):
			Keys.append(SortedFreqs[i][1])
		return Keys


class Solution:

	def TopK(self, arr, k):
		dic = {}
		for i in arr:
			try:
				dic[i] += 1
			except:
				dic[i] = 1
		l = list(dic.keys())
		l.sort(reverse=True)
		l.sort(key=lambda x: dic[x], reverse=True)
		return l[:k]


class Solution:

	def TopK(self, array, k):
		d = {}
		for i in range(len(array)):
			d[array[i]] = d.get(array[i], 0) + 1
		return sorted(d, key=lambda item: (d[item], item), reverse=True)[:k]


class Solution:

	def TopK(self, array, k):
		count = []
		hash_map = {}
		for i in array:
			if i in hash_map:
				hash_map[i] += 1
			else:
				hash_map[i] = 1
		x = list(hash_map.items())
		x.sort(reverse=True, key=lambda x: (x[1], x[0]))
		for j in range(k):
			count.append(x[j][0])
		return count


class Solution:

	def TopK(self, array, k):
		freq = {}
		for i in range(len(array)):
			if array[i] not in freq:
				freq[array[i]] = 1
			else:
				freq[array[i]] += 1
		ans = sorted(freq.keys(), key=lambda x: (freq[x], x), reverse=True)
		return ans[:k]


class Solution:

	def TopK(self, array, k):
		freq = {}
		for i in array:
			if i in freq:
				freq[i] += 1
			else:
				freq[i] = 1
		ResArr = []
		sorted_dict = sorted(freq.items(), key=lambda kv: (kv[1], kv[0]), reverse=True)
		for j in range(k):
			x = sorted_dict[j][0]
			ResArr.append(x)
		return ResArr


class Solution:

	def TopK(self, array, k):
		dict = {}
		result = []
		for val in array:
			if val in dict:
				dict[val] += 1
			else:
				dict[val] = 1
		temp = []
		for key in dict:
			temp.append((key, dict[key]))
		temp.sort(key=lambda x: x[0], reverse=True)
		temp.sort(key=lambda x: x[1], reverse=True)
		i = 0
		while k > 0:
			result.append(temp[i][0])
			k -= 1
			i += 1
		return result


from collections import Counter as co

class Solution:

	def TopK(self, a, k):
		dic = co(a).items()
		dum = sorted(dic, key=lambda x: (-x[1], -x[0]))
		re = []
		j = 0
		for i in dum:
			if j == k:
				break
			re.append(i[0])
			j += 1
		return re


class Solution:

	def TopK(self, array, k):
		arr = []
		for i in range(max(array) + 1):
			arr.append(0)
		for i in range(len(array)):
			arr[array[i]] += 1
		a = []
		b = []
		for i in range(len(arr)):
			a.append([i, arr[i]])
		a.sort(reverse=True, key=lambda a: (a[1], a[0]))
		for i in range(k):
			b.append(a[i][0])
		return b


class Solution:

	def TopK(self, array, k):
		count = {}
		for i in array:
			count[i] = count.get(i, 0) + 1
		li = sorted(count.items(), key=lambda x: [x[1], x[0]])
		li.reverse()
		ans = []
		for i in range(k):
			ans.append(li[i][0])
		return ans


class Solution:

	def TopK(self, arr, k):
		dic = {}
		for i in arr:
			if i in dic:
				dic[i] += 1
			else:
				dic[i] = 1
		res = []
		x = []
		for i in dic:
			res.append([i, dic[i]])
		res.sort(key=lambda x: x[0], reverse=True)
		res.sort(key=lambda x: x[1], reverse=True)
		for i in range(k):
			x.append(res[i][0])
		return x


class Solution:

	def TopK(self, a, K):
		hsh = dict()
		res = []
		for e in a:
			hsh[e] = hsh.get(e, 0) + 1
		val_key = [(v, k) for (k, v) in hsh.items()]
		val_key.sort(reverse=True)
		for (count, val) in val_key:
			res.append(val)
			K -= 1
			if K == 0:
				break
		return res


class Solution:

	def TopK(self, array, k):
		bin = dict()
		for i in array:
			bin[i] = bin.get(i, 0) + 1
		bintup = sorted([(v, k) for (k, v) in bin.items()], reverse=True)
		cust = list()
		for j in range(k):
			cust.append(bintup[j][1])
		return cust


class Solution:

	def TopK(self, array, k):
		flag = dict()
		for i in array:
			flag[i] = flag.get(i, 0) + 1
		K = sorted([(v, k) for (k, v) in flag.items()], reverse=True)
		res = list()
		for i in range(k):
			res.append(K[i][1])
		return res


class Solution:

	def TopK(self, array, k):
		d = dict()
		for i in array:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		l = []
		ans = []
		for i in d:
			l.append([d[i], i])
		l.sort(reverse=True)
		for i in range(k):
			ans.append(l[i][1])
		return ans


class Solution:

	def TopK(self, array, k):
		dic = {}
		lst = []
		for (i, a) in enumerate(array):
			if a in dic:
				dic[a] += 1
			else:
				dic[a] = 1
		for i in dic:
			lst.append((dic[i], i))
		lst.sort(reverse=True)
		ans = []
		for i in range(k):
			ans.append(lst[i][1])
		return ans


from collections import Counter

class Solution:

	def TopK(self, array, k):
		arr = []
		for (i, j) in dict(Counter(array)).items():
			arr.append([i, j])
		arr.sort(key=lambda a: (-a[1], -a[0]))

		def indx(a):
			return a[0]
		return list(map(indx, arr[:k]))


class Solution:

	def TopK(self, array, k):
		if k == 0:
			return []
		dict1 = {}
		for a in array:
			b = str(a)
			if b in dict1.keys():
				dict1[b] = dict1[b] + 1
			else:
				dict1[b] = 1
		l = sorted(dict1.items(), key=lambda x: (x[1], int(x[0])), reverse=True)
		ans = []
		count = 0
		for i in l:
			ans.append(i[0])
			count = count + 1
			if count == k:
				break
		return ans


import heapq

class Solution:

	def TopK(self, array, k):
		total = 10 ** 4 + 1
		ele_cnt = [0] * total
		for ele in array:
			ele_cnt[ele] += 1
		heap = []
		for ele in range(1, total):
			if ele_cnt[ele] > 0:
				heap.append((ele_cnt[ele], ele))
		del ele_cnt
		heapq.heapify(heap)
		ans = heapq.nlargest(k, heap)
		for i in range(len(ans)):
			ans[i] = ans[i][1]
		del heap
		return ans


class Solution:

	def TopK(self, array, k):
		d = dict()
		for i in range(len(array)):
			if array[i] not in d:
				d[array[i]] = 1
			else:
				d[array[i]] += 1
		l = list(d.items())
		l.sort(reverse=True)
		l.sort(key=lambda x: x[1], reverse=True)
		c = []
		for i in range(k):
			c.append(l[i][0])
		return c


class Solution:

	def TopK(self, array, k):
		count = dict()
		for i in array:
			count[i] = count.get(i, 0) + 1
		res = []
		for (key, value) in count.items():
			res.append((key, value))
		res.sort(key=lambda x: (x[1], x[0]), reverse=True)
		result = []
		for i in range(k):
			result.append(res[i][0])
		return result


from collections import Counter

class Solution:

	def TopK(self, array, k):
		counter = Counter(array)
		counter = sorted(counter.items(), reverse=True, key=lambda x: x[1])
		i = 1
		while i < len(counter):
			start = i - 1
			while i < len(counter) and counter[i][1] == counter[i - 1][1]:
				i += 1
			end = i
			counter[start:end] = sorted(counter[start:end], reverse=True)
			i += 1
		res = []
		for i in range(k):
			res.append(counter[i][0])
		return res


class Solution:

	def TopK(self, array, k):
		di = dict()
		for i in array:
			if i in di:
				di[i] += 1
			else:
				di[i] = 1
		lis = list()
		for i in di:
			lis.append([i, di[i]])
		lis.sort(reverse=True, key=lambda x: (x[1], x[0]))
		lis = [lis[i][0] for i in range(k)]
		return lis


class Solution:

	def TopK(self, array, k):
		dicti = {}
		for i in array:
			if i in dicti:
				dicti[i] += 1
			else:
				dicti[i] = 1
		listi = []
		st = set(array)
		for i in st:
			listi.append([dicti[i], i])
		listi.sort()
		listi = sorted(listi, reverse=True)
		res = []
		for i in range(k):
			res.append(listi[i][1])
		return res


from collections import Counter

class Solution:

	def TopK(self, array, k):
		dic = Counter(array)
		res_arr = []
		count = 0
		sorted_arr = sorted(dic.items(), key=lambda item: (item[1], item[0]), reverse=True)
		for item in sorted_arr:
			res_arr.append(item[0])
			count += 1
			if count == k:
				break
		return res_arr


class Solution:

	def TopK(self, array, k):
		d = dict()
		for i in array:
			d[i] = d[i] + 1 if d.get(i) else 1
		res = sorted(d, key=lambda k: (d[k], k), reverse=True)
		return res[:k]


from collections import defaultdict

class Solution:

	@staticmethod
	def default_value():
		return 0

	def comparator(self, x):
		return (self.d[x], x)

	def TopK(self, array, k):
		self.d = defaultdict(self.default_value)
		for x in array:
			self.d[x] += 1
		top_values = set(sorted(self.d.values(), reverse=True)[:k])
		return sorted((x for x in self.d.keys() if self.d[x] in top_values), key=self.comparator, reverse=True)[:k]


from collections import Counter

class Solution:

	def TopK(self, array, k):
		(mp, ans) = (Counter(array), [])
		arr = [(cnt, did) for (did, cnt) in mp.items()]
		arr.sort(reverse=True)
		for (_, did) in arr[:k]:
			ans.append(did)
		return ans


from collections import Counter

class Solution:

	def TopK(self, array, k):
		c = Counter(array).items()
		return [x[0] for x in sorted(c, key=lambda x: (x[1], x[0]), reverse=True)[0:k]]


import operator

class Solution:

	def TopK(self, array, k):
		count = dict()
		for i in array:
			count[i] = count.get(i, 0) + 1
		nl1 = sorted([(v, k) for (k, v) in count.items()], reverse=True)
		nl2 = list()
		for i in range(k):
			nl2.append(nl1[i][1])
		return nl2


class Solution:

	def TopK(self, array, k):
		dic = {}
		count = 0
		for elem in array:
			if elem in dic:
				dic[elem] += 1
			else:
				dic[elem] = 1
				count += 1
		arr2 = sorted(dic.items(), key=lambda k: (k[1], k[0]))
		out = []
		for i in range(k):
			out.append(arr2[count - i - 1][0])
		return out