There is a class of N students and the task is to find the top K marks scorers. You need to print the index of the toppers of the class which will be same as the index of the student in the input array (use 0-based indexing). First print the index of the students having highest marks then the students with second highest and so on. If there are more than one students having same marks then print their indices in ascending order.Suppose k = 2 and the students having highest marks have indices 0 and 5 and students having second highest marks have indices 6 and 7 then output will be 0 5 6 7.
Example 1:
Input:
N=5 K=3
arr[] = { 2, 2, 1, 3, 1 }
Output: 3 0 1 2 4
Explanation: Topper with 3 marks is present 
at 3rd index, 2 marks is present at 0^{th} 
index and next at 1^{st} index. 1 marks is present 
at 2 and 4.
Example 2:
Input:
N=4 K=1
arr[] = { 1, 2, 3, 4 } 
Output: 3
Explanation: The highest marks is at index 3.
Your Task:
Since this is a function problem. You don't need to take any input, as it is already accomplished by the driver code. You just need to complete the function kTop() that takes array A and integer N as parameters and change the given array according to the given conditions. You do not have to return anything
 
Expected Time Complexity: O(NlogN).
Expected Auxiliary Space: O(1).
 
Constraints:
1 ≤ N ≤ 10^{6}
1 ≤ M ≤ 10^{6}

Source: geeksforgeeks | Difficulty: EASY
Tags: Sorting

Data structures

Starter code: #User function Template for python3





def kTop(a,n):        

    # a is a 2D List which contains list of elemens like [marks. index]

    # Your code goes here

    









Solutions:
def kTop(a, n):
	a.sort(key=lambda x: x[0], reverse=True)


def kTop(a, n):
	a.sort(reverse=True)
	c = 0
	r = []
	a += [[-1, -1]]
	for i in range(len(a) - 1):
		if a[i][0] == a[i + 1][0]:
			r.append(a[i])
		else:
			r.append(a[i])
			r.sort(key=lambda x: x[1])
			k = 0
			for j in range(c, i + 1):
				a[j] = r[k]
				k += 1
			c = i + 1
			r = []


def kTop(a, n):

	def secondele(element):
		return element[0]
	a.sort(key=secondele, reverse=True)


def kTop(a, n):
	a.sort(key=lambda x: (-x[0], x[1]))


def kTop(a, n):
	a.sort(key=lambda x: (-x[0], x[1]))
	out = []
	for i in range(n):
		out.append(a[i][0])
		out.append(a[i][1])
	return out


from functools import cmp_to_key

def kTop(a, n):

	def f(a, b):
		if a[0] == b[0]:
			if a[1] < b[1]:
				return -1
			else:
				return 1
		elif a[0] > b[0]:
			return -1
		else:
			return 1
	a.sort(key=cmp_to_key(f))


def kTop(a, n):
	a.sort(reverse=True)
	idx = 0
	while idx < len(a) - 1:
		if a[idx][0] != a[idx + 1][0]:
			idx += 1
		else:
			idx_l = idx
			cur_ele = a[idx_l][0]
			cur_idx = idx_l
			while cur_idx + 1 < len(a) and a[cur_idx + 1][0] == cur_ele:
				idx_r = cur_idx + 1
				cur_idx = idx_r
			idx = idx_r
			while idx_l < idx_r:
				(a[idx_l], a[idx_r]) = (a[idx_r], a[idx_l])
				idx_l += 1
				idx_r -= 1


def cmp(a, b):
	pass

def kTop(a, n):
	a.sort(key=lambda x: (-x[0], x[1]))


def kTop(a, n):
	a.sort(key=lambda x: x[0], reverse=True)
	ans = []
	cnt = 0
	curr = a[0][0]
	for elem in a:
		if elem[0] != curr:
			cnt += 1
			if cnt == 3:
				break
		ans.append(elem[1])
	return ans


from collections import defaultdict

def kTop(a, n):
	a.sort(key=lambda x: -x[0])


def kTop(a, n):
	a.sort(key=lambda x: (-x[0], x[1]))
t = int(input())
for _ in range(0, t):
	n = int(input())
	s = list(map(str, input().split()))
	a = []
	k = int(input())
	for i in range(0, n):
		a.append([int(s[i]), i])
	kTop(a, n)
	i = 0
	for j in range(0, min(n, k)):
		x = a[i][0]
		while i < n and a[i][0] == x:
			print(a[i][1], end=' ')
			i = i + 1
		if i == n:
			break
	print()


from heapq import *

def kTop(a, n):
	ans = []
	for i in range(len(a)):
		heappush(ans, (-a[i][0], a[i][1]))
	c = 0
	while ans:
		k = heappop(ans)
		a[c] = k
		c += 1
t = int(input())
for _ in range(0, t):
	n = int(input())
	s = list(map(str, input().split()))
	a = []
	k = int(input())
	for i in range(0, n):
		a.append([int(s[i]), i])
	kTop(a, n)
	i = 0
	for j in range(0, min(n, k)):
		x = a[i][0]
		while i < n and a[i][0] == x:
			print(a[i][1], end=' ')
			i = i + 1
		if i == n:
			break
	print()


def kTop(a, n):
	d = dict()
	for i in range(n):
		if a[i][0] in d.keys():
			d[a[i][0]].append(a[i][1])
		else:
			d[a[i][0]] = [a[i][1]]
	d = sorted(d.items(), reverse=True)
	k = 0
	for i in range(len(d)):
		for j in range(len(d[i][1])):
			a[k] = [d[i][0], d[i][1][j]]
			k += 1


def kTop(a, n):
	_dict = {}
	for ai in a:
		_dict[ai[1]] = ai[0]
	sortedDict = sorted(_dict.items(), key=lambda kv: kv[1], reverse=True)
	idx = 0
	for item in sortedDict:
		a[idx][0] = item[1]
		a[idx][1] = item[0]
		idx += 1


def kTop(a, n):
	a.sort(key=lambda cx: (-cx[0], cx[1]))


def kTop(a, n):
	a.sort(key=lambda x: -x[0])
	return a


def kTop(Arr, N):
	a.sort(key=lambda x: (-x[0], x[1]))


def kTop(a, n):
	k = sorted(a, key=lambda x: x[0], reverse=True)
	for i in range(len(a)):
		a[i] = k[i]


def kTop(a, n):
	a.sort(key=lambda a: a[0], reverse=True)
	a = [i[1] for i in a]


def mergeSort(myList):
	if len(myList) > 1:
		mid = len(myList) // 2
		left = myList[:mid]
		right = myList[mid:]
		mergeSort(left)
		mergeSort(right)
		i = 0
		j = 0
		k = 0
		while i < len(left) and j < len(right):
			if left[i][0] >= right[j][0]:
				myList[k] = left[i]
				i += 1
			else:
				myList[k] = right[j]
				j += 1
			k += 1
		while i < len(left):
			myList[k] = left[i]
			i += 1
			k += 1
		while j < len(right):
			myList[k] = right[j]
			j += 1
			k += 1

def kTop(a, n):
	mergeSort(a)