Module: STL algorithms


Problem

5/6

std::nth_element

Theory Click to read/hide

nth_element is a function that allows you to find the nth element in an array in sorted order in linear time.
The function takes the left end of the array, an iterator to the position whose value in sorted order is to be found, and the right end of the array.
After applying the function, the required value will be located at the place indicated by the iterator, while the remaining values ​​will acquire a chaotic order, but to the left of the nth there will be values ​​no more than it, and to the right no less. That is, it should be understood that this function destroys the original order of the elements.
You can read more in the documentation (https://www.cplusplus.com/reference/algorithm/nth_element/).

Example: vector a = { 4, 0, 3, 9, 2, 1, 8, 5, 6, 7 }; // look for element at index 4 // pay attention to the order of the arguments nth_element(a.begin(), a.begin() + 4, a.end()); // a = [#, #, #, #, 4, $, $, $, $, $] // where # <= 4 and 4 <= $  

Problem

You are given q queries. Each request is given by an array of integers of size ni and a number k. You need to output the kth number in the sorted order of the given array.

Input:
The first line contains number q (1 <= q <= 20) - the number of queries.
The following is a description of the requests. 
For each query, the first line gives the size of the array ni (1 <= ni <= 5000) and the number k (1 <= k <= n i).
The next line contains ni integers - array elements, each of which does not exceed 109 in absolute value.

Output:
Print q numbers - the answers to the questions, each on a separate line.

Example:
 
Input Output
2
4 2
-5 3 4 3
3 3
-1 -2 -3 		3
-1


time 500 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Insert the missing code snippets
C++
Write the program below 
#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    int q;
	cin >> q;

	while (q--) {
		int n, k;
		cin >> n >> k;

		vector<int> arr(n);
		for (int i = 0; i < n; i++)
			cin >> arr[i]; 
	}
	
	return 0;
}

     

Program check result

To check the solution of the problem, you need to register or log in!