题解 | #最小的K个数#

import java.util.ArrayList;

public class Solution {
public ArrayList<integer> GetLeastNumbers_Solution(int [] input, int k) {
int find = -1;
int start = 0;
int end = input.length - 1;
while (find != k-1 && start<=end) {
find = intsertFistkey(input,start,end);
if (find > k-1) {
end = find - 1;
} else if (find < k-1) {
start = find + 1;
}
}
if (find != k-1) return new ArrayList<integer>();
ArrayList<integer> result = new ArrayList<integer>();
for (int l = 0;l<k;l++) {
result.add(input[l]);
}
return result;
}
int intsertFistkey(int[] input ,int start,int end) {
if (end <= start) return start;
int key = input[start];
int i = start;
int j = end;
int temp;
while (i<j) {
while(input[i] <= key && i<end) {
i++;
}
while(input[j] >= key && j>start) {
j--;
}
if (i<j) {
temp = input[i];
input[i] = input[j];
input[j] = temp;
}</integer></integer></integer></integer>

    }
    if (input[j] < key && j>start) {
        input[start] = input[j];
        input[j] = key;
        return j;
    }
    return start;
}

}