首页 > 代码库 > Lintcode: Kth Largest Element 解题报告

Lintcode: Kth Largest Element 解题报告

2024-08-08 01:18:46   219人阅读

Kth Largest Element

Find K-th largest element in an array.

Note

You can swap elements in the array

Example

In array [9,3,2,4,8], the 3th largest element is 4

Challenge

O(n) time, O(1) space

原题链接：

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

SOLUTION 1:

使用改进的Quicksort partition，可以达到O(n)的时间复杂度，并且不需要额外空间。

请参考： http://en.wikipedia.org/wiki/Quickselect#Time_complexity

 

时间复杂度：如果我们是这样的数组：1，2，3，4，5，然后又每一次取左边的当pivot，就会达到最坏的时间复杂度。也就是O(N2)

我们也有一些解决方法：

以下来自维基，我们可以取3个数进行平均。

http://stackoverflow.com/questions/7559608/median-of-three-values-strategy

The easiest solution is to choose a random pivot, which yields almost certain linear time. Deterministically, one can use median-of-3 pivot strategy (as in the quicksort), which yields linear performance on partially sorted data, as is common in the real world. However, contrived sequences can still cause worst-case complexity; David Musser describes a "median-of-3 killer" sequence that allows an attack against that strategy, which was one motivation for his introselect algorithm.

 1 package Algorithms.algorithm.NChapter.findKthNumber; 2  3 import java.util.ArrayList; 4  5 // The link:  6  7 // http://www.lintcode.com/en/problem/kth-largest-element/ 8  9 class KthLargestElement_lintCode {10     //param k : description of k11     //param numbers : array of numbers12     //return: description of return13     public int kthLargestElement(int k, ArrayList<Integer> numbers) {14         // write your code here15         if (k < 1 || numbers == null) {16             return 0;17         }18         19         return getKth(numbers.size() - k + 1, numbers, 0, numbers.size() - 1);20     }21     22     public int getKth(int k, ArrayList<Integer> numbers, int start, int end) {23         // Choose the last one as the pivot24         int pivot = numbers.get(end);25         26         int left = start;27         int right = end;28         29         while (true) {30             while (numbers.get(left) < pivot && left < right) {31                 left++;    32             }33             34             while (numbers.get(right) >= pivot && right > left) {35                 right--;36             }37             38             if (left == right) {39                 break;40             }41             42             swap(numbers, left, right);43         }44         45         // left: the first one which is bigger than pivot.46         swap(numbers, left, end);47         48         if (k == left + 1) {49             return pivot;50         // Try to find the element from the left side.51         } else if (k < left + 1) {52             return getKth(k, numbers, start, left - 1);53         } else {54         // Try to find the element from the right side.            55             return getKth(k, numbers, left + 1, end);56         }57     }58     59     /*60         Swap the two nodes.61     */62     public void swap(ArrayList<Integer> numbers, int n1, int n2) {63         int tmp = numbers.get(n1);64         numbers.set(n1, numbers.get(n2));65         numbers.set(n2, tmp);66     }67 };
View Code

 

SOLUTION 2:

以下这些链接有详细的讨论，就不再一一叙述了。目前来讲Solution 1应该是最优的啦。

http://www.geeksforgeeks.org/k-largestor-smallest-elements-in-an-array/

http://www.quora.com/What-is-the-most-efficient-algorithm-to-find-the-kth-smallest-element-in-an-array-having-n-elements

 

GITHUB:

https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/algorithm/NChapter/findKthNumber/KthLargestElement_lintCode.java

Lintcode: Kth Largest Element 解题报告


联系
我们