題目描述

輸入n個整數，找出其中最小的K個數。例如輸入4,5,1,6,2,7,3,8這8個數字，則最小的4個數字是1,2,3,4,。

思路1：利用快排的思想，尋找第k個位置上正確的數，k位置前面的數即是比k位置小的數組，k后面的數即是比k位置元素大的數組

public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {ArrayList<Integer> res = new ArrayList<Integer>();if (input==null||input.length==0||input.length<k||k<=0) {return res;}int start = 0;int end = input.length-1;int index = partition(input, start, end);//一直循環知道找到第k個位置正確的數。while (index != k - 1) {if (index > k - 1) {end = index-1;index = partition(input, start, end);} else {start = index+1;index = partition(input, start, end);}}for (int i = 0; i < k; i++) {res.add(input[i]);}return res;}static int partition(int input[], int start, int end) {int tmp = input[start];while (start < end) {while (start < end && input[end] >= tmp) {end--;}input[start] = input[end];while (start < end && tmp >= input[start]) {start++;}input[end] = input[start];}input[start] = tmp;return start;}思路2：利用堆排序，特別適用于海量數據中尋找最大或者最小的k個數字。即構建一個大堆容器，初始化大小為k，變量初始數，如初始數組大小小于等于k直接返回，如果大于k，則選擇數組的前k個元素，填充堆，然后調整為最大堆。調整完之后，繼續從初始數組中拿出一個元素，如果該元素比大堆的堆頂小，則替換堆頂，繼續調整為最大堆，如果大于等于堆頂則直接丟棄，不作調整。
PS：大堆還是小堆的選擇很重要，不是尋找最小的k個元素就要選擇小堆，而且恰恰相反。尋找最小的k個數，其實就是尋找第k個大的元素，即尋找k個數中最大的，不斷調整堆，堆得元素個數是k，堆頂是最大值，遍歷完初始數組后，堆中存在的元素即使我們所要尋找的k個最小元素。

//堆排序：構建堆，不斷調整的過程，從最后一個不是葉子節點的節點開始。static public ArrayList<Integer> GetLeastNumbers_Solution1(int[] input, int k) {ArrayList<Integer> res = new ArrayList<Integer>();if (input==null||input.length==0||input.length<k) {return res;}int []maxHeap = new int[k];//初始化堆for (int i = 0; i < maxHeap.length; i++) {maxHeap[i] = input[i];}//將初始化的堆調整為最大堆for (int i = (maxHeap.length-1)/2; i >=0 ; i--) {adjustHeap(maxHeap, i);}//遍歷初始數組不斷調整最大堆for (int i = k; i <input.length ; i++) {if (maxHeap[0]>input[i]) {maxHeap[0] = input[i];adjustHeap(maxHeap, 0);}}for (int i = 0; i < maxHeap.length; i++) {res.add(maxHeap[i]);}return res;}static void adjustHeap(int maxHeap[],int i){int index = i;int lchild=2*i+1; //i的左孩子節點序號 int rchild=2*i+2; //i的右孩子節點序號 if(index<=(maxHeap.length-1)/2) {//尋找子節點中最大的節點if (lchild<maxHeap.length&&maxHeap[index]<maxHeap[lchild]) {index = lchild;}if (rchild<maxHeap.length&&maxHeap[index]<maxHeap[rchild]) {index = rchild;}if (i!=index) {//將節點與最大的子節點交換int tmp = maxHeap[index];maxHeap[index] = maxHeap[i];maxHeap[i] = tmp;//交換后，子樹可能不滿足最大推，遞歸調整。adjustHeap(maxHeap, index);}}

總結

以上是生活随笔為你收集整理的寻找数组中最小的k个数(快排和堆排)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。