Andrew Chen

2021, 桃園林口三井

不太愛解題之隨手記錄

最簡單就是排序後找 k-th O(nlogn)

另一種想法是一個團體內,找年紀最大的,隨便拉一位以它為中央伍,問他比他大的分一群,小的也一群,從大群中繼續找,直到分不出群來。

k-th 也類似,就這個大群這個大小範圍內找,如果超出大群就去小群裡找

k - 大群量,得到一個新的 k' 到小群內找
  • 大群 mid ≤ num
  • 小群 num < mid

角落問題:如果碰巧分不出群來,就再找另一位中央伍,中央伍一定要跟別人不一樣才能分出群

直到分群剩下 1 個就是答案了。

空間可以改善的部分是 in-place ,是利用原本的 nums 置換,接著傳遞群邊界。

分三群,中央伍群,這樣好處是如果是落在中央伍群就可以離開了

  • 大群: mid < num
  • 中央群: mid == num
  • 小群: num < mid

網路上還有其他解法,像是 Heap (Priority Queue) ,有興趣可以看看。

--

--

2021 台灣玉山塔塔加鹿林山

題目有個第一版本,只差是完全二元樹,由於較簡單,這邊就直接先列第一版的答案,BJ4:

採用 DFS(深度優先),先做左子樹或右子樹都可以。

而第二版是不完全樹,這時就要考慮較多的事情。

root.right?.next = root.next?.left

由於是不完全樹,表示有可能會跨多個空子樹指右鄰,DFS 無法得知跨子樹的資訊,那麼需要依賴 root.next 來尋找跨樹右鄰,所以 DFS 至少我們會先完成右子樹。

connect(root.right)
connect(root.left)

接著要思考空子樹:

root.next == null
root.next.left == null

該怎麼辦?應該繼續往 root.next.next 找,再不行就一直繼續找,而且是要找到 root.next…..left 或者 root.next…right 為止。

fun getNext(root: Node?): Node? {
if (root == null) {
return root
}
return root.left ?: root.right ?: getNext(root.next)
}

這樣基本上就解決最大的難點了:

時間複雜度 O(2n)

getNext(): 每層跨度/寬度 k (k < n 節點),最糟狀況就是每層都耗 1k ,所以嚴苛來說時間複雜度是 O(2n)

這邊附上非遞迴的版本,思考框架是二維陣列:

var i = root
while (i != null) { // 往右移動
..
i = i.next
}

時間複雜度 O(n)

使用一維指標換行,這樣要自己換行:

時間複雜度 O(n)

--

--