十個元素最大的數組(尋找無序數組的第k大元素)
2023-05-06 18:44:54
戳藍字「CSDN雲計算」關注我們哦!
作者:小灰
來源:程式設計師小灰
本期封面作者:泰勒太樂
————— 第二天 —————
題目是什麼意思呢?比如給定的無序數組如下:
如果 k=6,也就是要尋找第6大的元素,這個元素是哪一個呢?
顯然,數組中第一大的元素是24,第二大的元素是20,第三大的元素是17 ...... 第6大的元素是9。
方法一:排序法
這是最容易想到的方法,先把無序數組從大到小進行排序,排序後的第k個元素,自然就是數組中的第k大元素。
方法二:插入法
維護一個長度為k的數組A的有序數組,用於存儲已知的k個較大的元素。
接下來遍歷原數組,每遍歷到一個元素,和數組A中最小的元素相比較,如果小於等於數組A的最小元素,繼續遍歷;如果大於數組A的最小元素,則插入到數組A中,並把曾經的最小元素「擠出去」。
比如k=3,先把最左側的7,5,15三個數有序放入數組A當中,代表當前最大的三個數。
這時候,遍歷到3, 由於35,插入到數組A的合適位置,類似於插入排序,並把原先最小的元素5「擠出去」。
繼續遍歷原數組,一直遍歷到數組的最後一個元素......
最終,數組A中存儲的元素是24,20,17,代表著整個數組中最大的3個元素。此時數組A中的最小的元素17就是我們要尋找的第k大元素。
————————————
什麼是二叉堆?不太了解的小夥伴可以先看看這一篇:漫畫:什麼是二叉堆?(修正版)
簡而言之,二叉堆是一種特殊的完全二叉樹,它包含大頂堆和小頂堆兩種形式。
其中小頂堆的特點,是每一個父節點都大於等於自己的子節點。要解決這個算法題,我們可以利用小頂堆的特性。
方法三:小頂堆法
維護一個容量為k的小頂堆,堆中的k個節點代表著當前最大的k個元素,而堆頂顯然是這k個元素中的最小值。
遍歷原數組,每遍歷一個元素,就和堆頂比較,如果當前元素小於等於堆頂,則繼續遍歷;如果元素大於堆頂,則把當前元素放在堆頂位置,並調整二叉堆(下沉操作)。
遍歷結束後,堆頂就是數組的最大k個元素中的最小值,也就是第k大元素。
假設k=5,具體的執行步驟如下:
1.把數組的前k個元素構建成堆。
2.繼續遍歷數組,和堆頂比較,如果小於等於堆頂,則繼續遍歷;如果大於堆頂,則取代堆頂元素並調整堆。
遍歷到元素2,由於 23,20取代堆頂位置,並調整堆。
遍歷到元素24,由於 24>5,24取代堆頂位置,並調整堆。
以此類推,我們一個一個遍曆元素,當遍歷到最後一個元素8的時候,小頂堆的情況如下:
3.此時的堆頂,就是堆中的最小值,也就是數組中的第k大元素。
這個方法的時間複雜度是多少呢?
1.構建堆的時間複雜度是 O(k)
2.遍歷剩餘數組的時間複雜度是O(n-k)
3.每次調整堆的時間複雜度是 O(logk)
其中2和3是嵌套關係,1和2,3是並列關係,所以總的最壞時間複雜度是O((n-k)logk k)。當k遠小於n的情況下,也可以近似地認為是O(nlogk)。
這個方法的空間複雜度是多少呢?
剛才我們在詳細步驟中把二叉堆單獨拿出來演示,是為了便於理解。但如果允許改變原數組的話,我們可以把數組的前k個元素「原地交換」來構建成二叉堆,這樣就免去了開闢額外的存儲空間。
因此,方法的空間複雜度是O(1)。
/**
* 尋找第k大的元素
* @param array 待調整的堆
* @param k 第幾大
*/
public static int findNumberK(int[] array, int k){
//1.用前k個元素構建小頂堆
buildHeap(array, k);
//2.繼續遍歷數組,和堆頂比較
for(int i=k; i array[0]){
array[0] = array[i];
downAdjust(array, 0, k);
}
}
//3.返回堆頂元素
return array[0];
}
/**
* 構建堆
* @param array 待調整的堆
* @param length 堆的有效大小
*/
private static void buildHeap(int[] array, int length) {
// 從最後一個非葉子節點開始,依次下沉調整
for (int i = (length-2)/2; i >= 0; i--) {
downAdjust(array, i, length);
}
}
/**
* 下沉調整
* @param array 待調整的堆
* @param index 要下沉的節點
* @param length 堆的有效大小
*/
private static void downAdjust(int[] array, int index, int length) {
// temp保存父節點值,用於最後的賦值
int temp = array[index];
int childIndex = 2 * index 1;
while (childIndex < length) {
// 如果有右孩子,且右孩子小於左孩子的值,則定位到右孩子
if (childIndex 1 < length && array[childIndex 1] < array[childIndex]) {
childIndex ;
}
// 如果父節點小於任何一個孩子的值,直接跳出
if (temp <= array[childIndex])
break;
//無需真正交換,單向賦值即可
array[index] = array[childIndex];
index = childIndex;
childIndex = 2 * childIndex 1;
}
array[index] = temp;
}
public static void main(String[] args) {
int array = new int {7,5,15,3,17,2,20,24,1,9,12,8};
System.out.println(findNumberK(array, 5));
}
方法四:分治法
大家都了解快速排序,快速排序利用分治法,每一次把數組分成較大和較小的兩部分。
我們在尋找第k大元素的時候,也可以利用這個思路,以某個元素A為基準,把大于于A的元素都交換到數組左邊,小於A的元素都交換到數組右邊。
比如我們選擇以元素7作為基準,把數組分成了左側較大,右側較小的兩個區域,交換結果如下:
包括元素7在內的較大元素有8個,但我們的k=5,顯然較大元素的數目過多了。於是我們在較大元素的區域繼續分治,這次以元素12位基準:
這樣一來,包括元素12在內的較大元素有5個,正好和k相等。所以,基準元素12就是我們所求的。
這就是分治法的大體思想,這種方法的時間複雜度甚至優於小頂堆法,可以達到O(n)。有興趣的小夥伴可以嘗試用代碼實現一下。
添加小編color_ld,備註「進群 姓名 公司職位」即可,加入【雲計算學習交流群】,和志同道合的朋友們共同打卡學習!
2.徵稿:
投稿郵箱:[email protected];color_ld。請備註投稿 姓名 公司職位。
,