题目：输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
/* 方法基本思路：使用快速排序，但不需要对整个数组进行排序，进去找到分区索引为k的元素，该元素左边k个数就是最小的k个数。 */ class Solution { public int[] getLeastNumbers(int[] arr, int k) { int left = 0; int right = arr.length-1; quickSort(arr,left,right,k); int[] res = new int[k]; for(int i = 0;i < k;i++){ res[i] = arr[i]; } return res; } public void quickSort(int[] arr,int left,int right,int k){ if(left > right){ return; } int index = getIndex(arr,left,right); if(index == k){ //不需要把整个数组排序，只需当分区索引为k时，它的左侧k个数就是最小的k个数，例如对于数组[0,1,2,3,4,5]，寻找到索引3的位置，左边3个数0，1，2就是最小的3个数。 return; } quickSort(arr,left,index-1,k); quickSort(arr,index+1,right,k); } public int getIndex(int[] arr,int left,int right){ int tmp = left; while(left<right){ while(left<right && arr[right]>=arr[tmp]){ right--; } while(left<right && arr[left]<=arr[tmp]){ left++; } if(left<right){ swap(arr,left,right); }else{ break; } } swap(arr,left,tmp); return left; } void swap(int[] arr,int i,int j){ int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } }