K-th smallest element in unsorted array

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 l such that k<=l and l is the length of the array v.
  • The second line consists of l numbers 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);
}

References


Related posts

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s