Shulou(Shulou.com)06/03 Report--

[topic description]

Find K-th largest element in an array.

Notice:You can swap elements in the array

Find the element with the largest k in the array

Note: you can swap the position of the elements in the array

[topic link]

Http://www.lintcode.com/en/problem/kth-largest-element/

[topic Analysis]

Sort's method: it must be very easy to see this problem at first, just sort it, and then return the value of a specific index, but the time complexity of sort is at least O (nlogn).

Quick Select: this is evolved from quick sort, using the part of partition, choose one pivot at a time, smaller than its left, larger than its right.

Using Quick Sort's divide-and-conquer method, or using Priority Queue (Max Heap) data structures, note that Java and Python are both minimum heaps and need to be converted.

[answer to the question]

Http://www.jiuzhang.com/solutions/kth-largest-element/

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.