這篇博客記錄我對劍指offer第2版"面試題39：陣列中出現次數超過一半的數字"題解1的一句話的一個小誤解，以及匯總一下涉及partition演算法的相關題目，
在劍指offer第2版"面試題39：陣列中出現次數超過一半的數字"的解法一(基于partition,且哨兵選擇陣列第一個元素)中,有這么一句話:
我們有成熟的時間復雜度為O(n)的演算法得到陣列中任意第k大的數字,這句話讓我產生了一點誤解,讓我誤以為"只需要呼叫一次partition就能找到第k大的數",但是實際上最差情況下需要呼叫n次partition函式才能找到第k大的數，因為partition每次都回傳的是哨兵的位置,但是在函式運行程序中,隨著l,r入參的變化,哨兵(陣列首位元素)的位置是隨之變化的,具有不確定性，
所以基于partition獲取陣列中任意第k大元素的時間復雜度應該如下:
- 最好時間復雜度 O(1) : 第一次回圈就找到正確的哨兵(即,第k大元素)
- 最差時間復雜度 n*O(n): 最后一次才找到正確的哨兵
- (加權)平均復雜度 這個我不太會算，估計是O(n)
估算程序:
3.1 加權平均復雜度 = 某概率值*O(n)
3.2 概率值是常數，然后去掉常數項，得O(n)
partition的Go代碼如下:
// partition代碼的時間復雜度是O(n),因為需要通過for回圈遍歷陣列，并把每個元素都劃分到大磁區或小磁區中，
func partition(nums []int, l, r int) int {
// 1. 哨兵 取第一個元素
v := nums[l]
// 2. 大小磁區的定義和初始化 [l+1,p]<v && [p+1,cur-1]>v
p := l
// 3. 處理哨兵之后的每一個元素
cur := l + 1
for ; cur <= r; cur++ {
if nums[cur] < v {
nums[cur], nums[p+1] = nums[p+1], nums[cur]
p++
}
}
nums[p], nums[l] = nums[l], nums[p] // 哨兵和小磁區的最后一個元素交換,使得哨兵左邊是小的,右邊是大的.
return p
}
另外，還有以下這些演算法題涉及了partition函式的運用,他們的共同特點都是需要用partition查找xxx位置的數字，
- Majority Element(本博客討論的題) : partition查找m位置的數(中位數:索引為n/2)
- Kth Largest Element in an Array : partiton查找k位置的數
- 劍指offer面試題40：最小的k個數 : partiton查找k位置的數,但是只回傳k位置左邊的數,也就是小于哨兵的那些數
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/113010.html
標籤：其他
上一篇：Leetcode 與樹(TreeNode )相關的題解測驗工具函式總結
下一篇：資料結構期末考試復習--1