原文見(jiàn)：https://mp.weixin.qq.com/s/g4Y6ES4eL9cKJKkSpGZFYg

順序統(tǒng)計(jì)之第K大元素

問(wèn)題

Given an array and a number k where k is smaller than size of array, we need to find the k’th smallest element in the given array. It is given that ll array elements are distinct.

解法

對(duì)數(shù)據(jù)進(jìn)行排序

時(shí)間復(fù)雜度：O(N Log N)

借助一個(gè)大小為N的最大堆，然后extractMax k次

時(shí)間復(fù)雜度：O(kLogN)

借助一個(gè)大小為K的最小堆

時(shí)間復(fù)雜度：O(NLogK)

空間復(fù)雜度：O(K)

利用快排的partition函數(shù)，將數(shù)組分為兩部分，大小分別為i以及n-i（假設(shè)i>k) ;問(wèn)題轉(zhuǎn)換為數(shù)組arr[0, i]中取第K-i大元素

時(shí)間復(fù)雜度：平均 O（N）；最壞O(N^2)

隨機(jī)版本的quickSelect

時(shí)間復(fù)雜度：期望O(N) 最壞依舊是O(N^2)

每5個(gè)為一組，并取其中位數(shù)；然后在中位數(shù)中取出pivot;

時(shí)間復(fù)雜度：最壞O(N)

總結(jié)

快排思想很重要

快排partition函數(shù)的優(yōu)化思想更重要（隨機(jī)化，分組取中法）

TopK問(wèn)題的經(jīng)典解法可以靠堆來(lái)解決