Last Updated: 2 Mar, 2021
First K Maximum Elements
Easy
Asked in companies
You have been given an array of ‘N’ integers and an integer 'K'. You have to find the indexes of the first 'K' maximum elements in the array.
Note :
'K' must be less than or equal to the number of distinct elements in the given array.
Consider '0’ based indexing of the elements in the given array.
Print all indexes in increasing order.
For Example :
If, 'ARR' = [4, 2, 4, 2, 1], and K = 2. Then output will be 0, 1, 2, 3.
Input Format :
The first line contains a single integer ‘T’ representing the number of test cases.
The first line of each test case will contain two space-separated integers ‘N’ and 'K' where ‘N’ is the length of the array, and 'K' is the integer which is described above.
The second line of each test case will contain ‘N’ space-separated integers which denote the elements in the given array.
Output Format :
For each test case, print the indexes of the first 'K' maximum elements in the increasing order.
Output for every test case will be printed in a separate line.
Note :
You don’t need to print anything; It has already been taken care of. Just implement the given function.
There is no need to sort the indexes in increasing order it has already been taken care of.
Constraints :
1 <= T <= 50
1 <= N <= 10000
1 <= K <= Distint Element in ARR
0 <= ARR[i] <= 10 ^ 5
Where 'ARR[i]' is the i'th element of the given array.
Time limit: 1 sec
Approaches
The basic idea is to put all the elements in a set and arrange them in decreasing order, then find the indexes of the first ‘k’ maximum elements in the input array.
The steps are as follows:
- Create a set (say, “st”) to store all the distinct elements in decreasing order and a variable named “count” to count the maximum elements traced.
- Create a vector of type int (say, “ans”) to store the indexes of maximum elements.
- Iterate through the “arr” and keep storing each element into “st”.
- Iterate through the “st” (say, iterator = ‘i’).
- Increment the “count” by 1 and check if “count” becomes greater than ‘k’ then stops the further iterations.
- Iterate through the “arr” and check if the element at any iteration is equal to the element in “st” at ‘i’ then push its index into the “ans”.
- Returns the vector “ans”.
The basic idea is to sort the given array in decreasing order by keeping the indexes of each element secured (done by using pair) and then print the first ‘k’ distinct elements.
Here, we will be going to use a custom sorting function named “cmp”.
bool cmp(pair<int,int> p1, pair<int,int> p2)Where ‘p1’ and ‘p2’ stores the two different positioned elements of the array at first and at the second it stores their indexes.
The steps are as follows:
- Inside the “cmp” function:
- If elements stored in the pairs ‘p1’ and ‘p2’ are the same then return ‘p1’.second < ‘p2’.second.
- Otherwise, returns ‘p1’.first > ‘p2’.first.
- In the given function:
- Create a vector of pairs (say, ‘v’) and store each element along with its indexes in the ‘v’. Make sure to store element at first and index at second.
- Sort the vector ‘v’ according to the function “cmp”.
- Create a variable to store the number of distinct elements processed and initialise it with 1. (say, “count”)
- Create another vector “ans” to store the indices of maximum elements.
- Insert the index of the first element stored in ‘v’ into the “ans”.
- Now, iterate through the vector ‘v’ from 1 to the end. (say, iterator = ‘i’)
- If, element stored at index ‘i’ in ‘v’ is the same as at index ‘i’ - 1, then insert it’s index into the “ans”.
- Otherwise, increment “count” by 1 and check if “count” becomes greater than “k” then break the loop. Else, add the index of the element at ‘i’ into the “ans”.
- Return the vector “ans”.
Similar problems