import java.util.ArrayList; public class Solution { public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) { ArrayList<Integer> res = new ArrayList<>(k); int len = input.length; for(int i = len/2 - 1;i >= 0; --i) { adjust(input,i,len); } for(int i = len-1; i >= len -k; --i) { res.add(input[0]); swap(input,0,i); adjust(input,0,i); } return res; } // 找出最小的k个数 void adjust(int[] arr, int pos, int end) { int child = 2*pos + 1; int tmp = arr[pos]; for(int k = 2*pos + 1; k < end; k = 2*k + 1){ if(k+1 < end && arr[k+1] < arr[k]) { k++; } if( k < end && arr[k] < tmp) { arr[pos] = arr[k]; pos = k; }else { break; } } arr[pos] = tmp; } void swap(int[] arr,int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } // 找出最大的k个数 void adjust2(int[] arr, int pos, int end) { int child = 2*pos + 1; int tmp = arr[pos]; for(int k = 2*pos + 1; k < end; k = 2*k + 1){ if(k+1 < end && arr[k+1] > arr[k]) { // 修改 k++; } if( k < end && arr[k] > tmp) { // 修改 arr[pos] = arr[k]; pos = k; }else { break; } } arr[pos] = tmp; } }