Given an array v of distinct numbers, and a number k where k is smaller than the size of v, find the k-th smallest element in the array. A simple solution would be first sorting the array in growing order and than selecting the k-th element which can be done in θ(n logn). However, your program MUST run in θ(n) on average.
Difficulty: Medium.
Input
There are two lines.
- The first line contains an integer
k - The second line contains an integer
lsuch thatk<=landlis the length of the array v. - The second line consists of
lnumbers separated by space which represent the array v.
At the end of each line, there are no extra spaces, and there is a \n.
Output
One line containing 1 integer, which is the k-th smallest number in v.
Example
Input:
3
5
3 5 2 8 4
Output:
4
Hint
You can borrow the idea of Quicksort.
Solution: C++
#include<stdlib.h>
#include<stdio.h>
#include<iostream>
using namespace std;
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
int partition(int v[], int l, int r){
// same as quicksort
int p = v[r-1]; // pivot is the last element
int j=l;
for(int i=l;i<r-1;i++){
if(v[i]<p){
swap(&v[i], &v[j]);
j++;
}
}
swap(&v[j], &v[r-1]);
return j;
}
void find_k_smallest(int v[], int k, int l, int r){
//find the pivot such that v[0...p-1]<v[p]<v[p+1...l]
int p = partition(v, l, r);
//if the pivot is the k-th element, we are done since v[0...k-1]<v[k]<v[k+1...l]
if(p==k-1){
cout<<v[p];
return;
}
//the solution is in v[0...p-1]
if(p>k-1)
find_k_smallest(v, k, l, p);
//the solution is in v[p+1...l]
find_k_smallest(v, k, p+1, r);
}
int main(){
int k;
cin>>k; //index k of the k-th smallest number in the array
int l;
cin>>l; //length of the array
int v[l];
for(int i=0; i<l; i++)
cin>>v[i];
find_k_smallest(v, k, 0, l);
}
KejiTech 