# 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];
}