【題目描述】
Find K-th largest element in an array.
Notice:You can swap elements in the array
在陣列中找到第k大的元素
注意：你可以交換陣列中的元素的位置
【題目鏈接】
http://www.lintcode.com/en/problem/kth-largest-element/
【題目決議】
sort的方法：一開始看到這道題肯定覺得很簡單，只要sort一下，然后return特定index的value就可以了，但是sort的time complexity至少是O（nlogn)
Quick Select：這個是由quick sort演化而來，用到了partition的部分，每次選一個pivot,小于它的放左邊，大于它的放右邊。
用Quick Sort的divide-and-conquer法，或者用Priority Queue (Max Heap) 資料結構，注意Java和Python都是最小堆，需要轉換一下。
【題目答案】
http://www.jiuzhang.com/solutions/kth-largest-element/
uj5u.com熱心網友回復：
利用 List 控制元件的奇葩解法：設定其中 List2 的 Sorted = True下面的例子是從 100 個亂數中找出第 5 大的數字。
List2.List(0) 就是問題的解。
Private Const K = 5
Private Const N = 100
Private Sub Command1_Click()
Dim i As Integer
'Prerare data
List1.Clear
Randomize
For i = 1 To N
List1.AddItem Rnd * 1000
Next i
'Find Kth Largest Number
List2.Clear
For i = 0 To N - 1
If List2.ListCount < K Then
List2.AddItem List1.List(i)
Else
If List1.List(i) > List2.List(0) Then
List2.RemoveItem 0
List2.AddItem List1.List(i)
End If
End If
Next i
End Sub
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/60956.html
標籤：非技術類