The Least k Numbers

Question: Please find out the least k numbers out of n numbers. For example, if given the 8 numbers 4, 5, 1, 6, 2, 7, 3 and 8, please return the least 4 numbers 1, 2, 3 and 4.
Analysis: The naïve solution is sort the n input numbers increasingly, and the least k numbers should be the first k numbers. Since it needs to sort, its time complexity is O(nlogn). Interviewers will ask us explore more efficient solutions.

1.    use a k data container, and take first k numbers in. then compare the max in the container with the coming numbers, if coming number is smaller then replace. otherwise, next.

 if we use binary search tree, find&insert&delete would be logk, , the complexity would be O(nlogk).
 If max heap, O(1) to get max, but logk to insert and delete.

2. use the partition function which returns the index of pivot in quick sort.

 until we get the index = k-1, we have all the k-1 numbers in the left which are smaller than the pivot(kth number).
void GetLeastNumbers(int[] input, int n, int[] output, int k)
{
    if(input == NULL || output == NULL || k > n || n <= 0 || k <= 0)
        return;
    int start = 0;
    int end = n – 1;
    int index = Partition(input, n, start, end);
    while(index != k – 1)
    {
        if(index > k – 1)
        {
            end = index – 1;
            index = Partition(input, n, start, end);
        }
        else
        {
            start = index + 1;
            index = Partition(input, n, start, end);
        }
    }
    for(int i = 0; i < k; ++i)
        output[i] = input[i];
}

Advertisements

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s