生活随笔
收集整理的這篇文章主要介紹了
数据结构与算法--最小的k个数
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
最小的k個數
- 題目：輸入n個整數，找出其中最小的k個數，例如輸入4,5，6,7，8,9這六個數字，則最小的4個是4,5，6,7
方案一
- 還是最直觀的方法，先排序，最快的是快排O(nlog2n)，然后遍歷前面k個數組，得到我們需要的答案，這個最簡單方案應該有更優實現
方案二
- 題意，我們需要找出最小的k個數字，還是從快排的思路收到啟發
- 我們同樣基于快速排序，但是只找出第k個大的數字
- 因為快排過程中會將比基準值小的放到 之前，比基準值大的放到后面，因此只需要找到第k個大的數字，在之前的數就是我們需要的數
- 基于如上分析有如下代碼：
public class GetLeastNumbers {public static void main(String[] args
) {Integer[] arrayData
= new Integer[20];Random random
= new Random();for (int i
= 0; i
< 20; i
++) {arrayData
[i
] = random
.nextInt(50);System.out
.print(arrayData
[i
]+",");}System.out
.println();Integer[] newArray
= getLeastNumbers(arrayData
, 10);for (Integer integer
: newArray
) {System.out
.print(integer
+",");}}public static Integer[] getLeastNumbers(Integer[] array
, Integer key
) {if (array
== null || array
.length
<= 0 || array
.length
< key
) {return new Integer[]{};}if (array
.length
== key
) {return array
;}return quickSort(array
, 0, array
.length
-1, key
);}public static Integer[] quickSort(Integer[] array
, Integer left
, Integer right
, Integer key
) {if (left
< right
) {Integer middle
= quickSortSwap(array
, left
, right
);if (middle
== key
) {return Arrays.copyOfRange(array
, 0, key
);}quickSort(array
, left
, middle
- 1, key
);quickSort(array
, middle
+ 1, right
, key
);}return Arrays.copyOfRange(array
, 0, key
);}public static Integer quickSortSwap(Integer[] array
, Integer left
, Integer right
) {if (left
< right
) {Integer position
= array
[left
];while (left
< right
) {while (left
< right
&& array
[right
] > position
) {right
--;}if (left
< right
) {array
[left
] = array
[right
];left
++;}while (left
< right
&& array
[left
] < position
) {left
++;}if(left
< right
){array
[right
] = array
[left
];right
--;}}array
[left
] = position
;}return left
;}
}
- 基于快排的方案是有限制的，因為我們需要修改輸入的數組，最后的順序是變化的，如果要求不能修改輸入的參數，我們是否有其他方案。
方案三
- 既然不能修改原值，那么我們復制一個我們需要的值，還是空間換時間的做法
- 我們建一個原數組大小的容器用來存儲，接著在容器中找出最小的k個數
- 本次我們需要的存儲的特點是能快速的找到最小值，這樣重復查找k次最小值，就能得到結果
- 如果我們用二叉查找樹來實現這個容器，那么我們每次查詢的時間復雜度是O(logn)，也就是層高度，那么k次查詢就是O(klogn)
- 但是還有其他變種的二叉查找樹二叉堆中對小堆，之前文章：數據結構與算法–二叉堆（最大堆，最小堆）實現及原理對最大堆，最小堆的實現有詳細的解釋
- 最小堆的特點在于能在O(1)時間內找到最小值，就是二叉堆的根節點
- 并且二叉堆的結構特性就在于能夠快速的查詢，我們將所有數據構造成一個最小堆，然后經k次O(1)的操作，就能得到結果
- 經如上分析有如下代碼：
public class GetLeastNumbers {public static void main(String[] args
) {Integer[] arrayData
= new Integer[20];Random random
= new Random();for (int i
= 0; i
< 20; i
++) {arrayData
[i
] = random
.nextInt(50);System.out
.print(arrayData
[i
]+",");}System.out
.println();Integer[] heapArray
= getLeastNumbersByBinaryHeapMax(arrayData
, 10);for (int i
= 0; i
< heapArray
.length
; i
++) {System.out
.print(heapArray
[i
]+",");}}public static Integer[] getLeastNumbersByBinaryHeapMax(Integer[] array
, Integer key
){if (array
== null || array
.length
<= 0 || array
.length
< key
) {return new Integer[]{};}if (array
.length
== key
) {return array
;}Integer size
= (array
.length
+ 2 )*11/10;BinaryHeap binaryHeap
= new BinaryHeap(size
);for (int i
= 0; i
< array
.length
; i
++) {binaryHeap
.insert(new AnyType(array
[i
]));}Integer[] result
= new Integer[key
];for (Integer i
= 0; i
< key
; i
++) {result
[i
] = Integer.valueOf(binaryHeap
.deleteMin().getElement().toString());}return result
;}
}
方案四
- 如上最小堆的實現中雖然找最小值都是O(1)，但是在構造最小堆的過程中我們需要O(logn)的時間復雜度，如果題目要是海量數據，其實我們也可以用最大堆
- 我們可以用k個元素的最大堆，當堆滿后，每次讀入原數組中一個數據，與最大數據比較（O(1)時間）
- 如果比最大數據要小，我們刪除最大數據，插入當前值，直到整個數組遍歷完
- 此時得到的最大堆中k個數據就是我們需要的數據
- 這種方案可以用來處理海量數據時候內存占用過多的問題。
- 海量數據情況下，空間復雜度O(k)的實現方式如下：
public class GetLeastNumbers {public static void main(String[] args
) {Integer[] arrayData
= new Integer[20];Random random
= new Random();for (int i
= 0; i
< 20; i
++) {arrayData
[i
] = random
.nextInt(50);System.out
.print(arrayData
[i
]+",");}System.out
.println();Integer[] maxArray
= getLeastNumberByBinaryHeapMax(arrayData
, 10);for (Integer integer
: maxArray
) {System.out
.print(integer
+",");}}public static Integer[] getLeastNumberByBinaryHeapMax(Integer[] array
, Integer key
){if (array
== null || array
.length
<= 0 || array
.length
< key
) {return new Integer[]{};}if (array
.length
== key
) {return array
;}Integer size
= (array
.length
+2)*11/10;BinaryHeapMax binaryHeapMax
= new BinaryHeapMax(size
);for (int i
= 0; i
< array
.length
; i
++) {AnyType anyType
= new AnyType(array
[i
]);if(binaryHeapMax
.heapSize() >= key
){Integer heapMax
= Integer.valueOf(binaryHeapMax
.findMax().getElement().toString());if(array
[i
] < heapMax
){binaryHeapMax
.deleteMax();binaryHeapMax
.insert(anyType
);}}else {binaryHeapMax
.insert(anyType
);}}AnyType[] anyTypes
= binaryHeapMax
.getAppHeapData();Integer[] result
= new Integer[key
];for (int i
= 0; i
< anyTypes
.length
; i
++) {result
[i
] = Integer.valueOf(anyTypes
[i
].getElement().toString());}return result
;}
}
解法對比
- 第一種方案直接排序遍歷平均時間復雜度是O(nlog2n)，比第二種思路上更容易理解，但是同時也有明顯的限制會修改入參數組
- 第二種解法，也是基于快排思路，但是可以在中間退出，因此時間復雜度小于O(nlog2n)，同樣也會修改入參數組
- 第三種方法，最小堆的方式，先構建最小堆，在讀取，這種有兩個明顯優點，一個是沒有修改輸入的數據，因為我們只是讀取入參數組中的數字，所有寫操作都是在最小堆中完成，二是解法簡單，缺點也明顯，時間復雜度更大，構建時候需要insert，n次，每次insert的平均時間復雜度是O(logn)，因此是O(nlogn)
- 第四種算法適合海量數據的輸入，如果題目要求的是海量數數據中找k個數，內存的大小限制，不可能全讀取如內存，這時候，我們只一次讀取一個數據進內存，只要求內存容納的下最大堆中的k個數據即可，能有效解決n很大，k很小的情況，時間復雜度也是O(nlogk)
上一篇：數據結構與算法–兩個鏈表中第一個公共節點
下一篇：數據結構與算法–數字在排序數組中出現次數
總結
以上是生活随笔為你收集整理的数据结构与算法--最小的k个数的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
