?

?

解題思路：

乘著做這個(gè)題，順便復(fù)習(xí)下堆排序。

先說(shuō)堆排序是一個(gè)什么東西：https://blog.csdn.net/u013384984/article/details/79496052

大頂堆升序，小頂堆降序。

隨便定義的一個(gè)堆。

?

第一步：

此時(shí)我們從最后一個(gè)非葉子結(jié)點(diǎn)開(kāi)始（葉結(jié)點(diǎn)自然不用調(diào)整，第一個(gè)非葉子結(jié)點(diǎn) arr.length/2-1=5/2-1=1，也就是下面的6結(jié)點(diǎn)），從左至右，從下至上進(jìn)行調(diào)整。

此處必須注意，我們把6和9比較交換之后，必須考量9這個(gè)節(jié)點(diǎn)對(duì)于其子節(jié)點(diǎn)會(huì)不會(huì)產(chǎn)生任何影響？因?yàn)槠涫侨~子節(jié)點(diǎn)，所以不加考慮；但是，一定要熟練這種思維，寫代碼的時(shí)候就比較容易理解為什么會(huì)出現(xiàn)一次非常重要的交換了。

?

?

?注意：第一步已經(jīng)把9弄上去了，所以只需要看9 5 6這三個(gè)數(shù)字是不是符合大頂堆，一看符合的，然后回到4.找到第二個(gè)非葉節(jié)點(diǎn)4，由于[4,9,8]中9元素最大，4和9交換。

牢記上面說(shuō)的規(guī)則，每次交換都要把改變了的那個(gè)節(jié)點(diǎn)所在的樹(shù)重新判定一下，這里就用上了，4和9交換了，變動(dòng)了的那棵子樹(shù)就必須重新調(diào)整，一直調(diào)整到符合大根堆的規(guī)則為截。

此時(shí)，我們就將一個(gè)無(wú)序序列構(gòu)造成了一個(gè)大頂堆。

步驟二 將堆頂元素與末尾元素進(jìn)行交換，使末尾元素最大。然后繼續(xù)調(diào)整堆，再將堆頂元素與末尾元素交換，得到第二大元素。如此反復(fù)進(jìn)行交換、重建、交換。

a.將堆頂元素9和末尾元素4進(jìn)行交換

這里，必須說(shuō)明一下，所謂的交換，實(shí)際上就是把最大值從樹(shù)里面拿掉了，剩下參與到排序的樹(shù)，其實(shí)只有總結(jié)點(diǎn)的個(gè)數(shù)減去拿掉的節(jié)點(diǎn)個(gè)數(shù)了。所以圖中用的是虛線。

?

注意：這里和root交換后的東西，后面已經(jīng)不放在堆里面進(jìn)行排了。

1 import java.util.ArrayList; 2 public class Solution { 3 public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) { 4 5 ArrayList<Integer> res = new ArrayList<>(); 6 7 if(k>input.length || input==null) 8 return res; 9 // 按照完全二叉樹(shù)的特點(diǎn)，從最后一個(gè)非葉子節(jié)點(diǎn)開(kāi)始，對(duì)于整棵樹(shù)進(jìn)行大根堆的調(diào)整 10 // 也就是說(shuō)，是按照自下而上，每一層都是自右向左來(lái)進(jìn)行調(diào)整的 11 // 注意，這里元素的索引是從0開(kāi)始的 12 // 另一件需要注意的事情，這里的建堆，是用堆調(diào)整的方式來(lái)做的 13 // 堆調(diào)整的邏輯在建堆和后續(xù)排序過(guò)程中復(fù)用的 14 for(int i=k/2-1;i>=0;i--) 15 { 16 Adjust(input,i,k-1);//從最后一個(gè)非葉子節(jié)點(diǎn)開(kāi)始 17 } 18 19 for(int j=k;j<input.length;j++) 20 { 21 // 元素交換之后，毫無(wú)疑問(wèn)，最后一個(gè)元素?zé)o需再考慮排序問(wèn)題了。 22 // 接下來(lái)我們需要排序的，就是已經(jīng)去掉了部分元素的堆了，這也是為什么此方法放在循環(huán)里的原因 23 // 而這里，實(shí)質(zhì)上是自上而下，自左向右進(jìn)行調(diào)整的 24 if(input[j]<input[0]) 25 { 26 int temp = input[0]; 27 28 input[0] = input[j]; 29 30 input[j] = temp; 31 32 Adjust(input,0,k-1); 33 } 34 } 35 36 for(int i=0;i<k;i++) 37 { 38 res.add(input[i]); 39 } 40 return res; 41 } 42 public void Adjust(int [] input,int k,int length) 43 { 44 int temp = input[k]; 45 46 for(int i=2*k+1;i<=length;i=2*i+1)//i是子節(jié)點(diǎn) 47 { 48 if(i<length && input[i]<input[i+1]) 49 i++; 50 51 if(temp>input[i]) 52 { 53 break; 54 } 55 else 56 { 57 swap(input, i, k); 58 // 下面就是非常關(guān)鍵的一步了 59 // 如果子節(jié)點(diǎn)更換了，那么，以子節(jié)點(diǎn)為根的子樹(shù)會(huì)不會(huì)受到影響呢？ 60 // 所以，循環(huán)對(duì)子節(jié)點(diǎn)所在的樹(shù)繼續(xù)進(jìn)行判斷 61 k = i; 62 } 63 } 64 } 65 66 public void swap(int []input,int a,int b) 67 { 68 int temp = input[a]; 69 input[a]=input[b]; 70 input[b] = temp; 71 } 72 73 74 }

?

1 class Solution { 2 public int findKthLargest(int[] input, int k) { 3 4 if(input.length==1) 5 return input[0]; 6 int length = input.length; 7 for(int i=k/2-1;i>=0;i--) 8 { 9 Adjust(input,i,length-1); 10 } 11 12 for(int j = length - 1; j >=k; j--) 13 { 14 if(input[j]>input[0]) 15 { 16 int temp = input[0]; 17 input[0] = input[j]; 18 input[j] = temp; 19 Adjust(input,0,k-1); 20 } 21 } 22 23 return input[0]; 24 25 26 } 27 28 public void Adjust(int []input,int k,int length) 29 { 30 int temp = input[k]; 31 for(int i=2*k+1;i<=length;i=2*i+1) 32 { 33 if(i<length && input[i]>input[i+1]) 34 { 35 i++; 36 } 37 if(temp<input[i]) 38 { 39 break; 40 } 41 else 42 { 43 swap(input,i,k); 44 k=i; 45 } 46 47 } 48 } 49 50 public void swap(int []input,int a,int b) 51 { 52 int temp = input[a]; 53 input[a]=input[b]; 54 input[b] = temp; 55 } 56 57 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/wangyufeiaichiyu/p/11054807.html

總結(jié)

以上是生活随笔為你收集整理的剑指offer——最小的K个数和数组中第K大的元素的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。