题目描述
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
ArrayList<Integer> array = new ArrayList<Integer>();
if(k > input.length){
return array;
}
qSort(input, 0, input.length - 1);
for(int i = 0; i < k; i++){
array.add(input[i]);
}
return array;
}
public void qSort(int[] a, int left, int right) {
if(left >= right) {
return;
}
int val = a[left];
int i = left;
int j = right;
while(i < j) {
while(j > i){
if(a[j] < val)
break;
else
j--;
}
while(i < j) {
if(a[i] > val)
break;
else
i ++;
}
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
a[left] = a[i];
a[i] = val;
qSort(a, left, i - 1);
qSort(a, i + 1, right);
}
public static void main(String[] args) {
Solution obj = new Solution();
int [] array = {1,3,2,5,6,5};
obj.qSort(array, 0, array.length - 1);
for(int i : array){
System.out.println(i);
}
}
}
