S*******C
发帖数: 822 | 1 以下的O(n) time, O(1) space解法还能再简化吗？
Kth Largest Element
18%
Accepted
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 3rd largest element is 4
In array [1,2,3,4,5], the 1st largest element is 5, 2nd largest element is 4
, 3rd largest element is 3 and etc.
Challenge
O(n) time, O(1) space
class Solution {
public static void main(String args[]) {
Solution test = new Solution();
int[] a = { 5, 4, 1, 3, 2};
ArrayList list = new ArrayList();
for (int i : a)
list.add(i);
for (int i = 1; i <= a.length; i++)
System.out.println(test.kthLargestElement(i, list));
}
//param k : description of k
//param numbers : array of numbers
//return: description of return
public int kthLargestElement(int k, ArrayList list) {
if (list == null || list.size() < k)
throw new Error("The kth largest element does not exist in given
list");
int start = 0, end = list.size() - 1;
k = list.size() - k;//comment this statement to find kth smallest
element
// if start == end we reached the kth element
while (start < end) {
int low = start, high = end, mid = (low + high) / 2;
int pivot = list.get(mid);
while (low < high) {
if (list.get(low) >= pivot) { // put large values at the end
int temp = list.get(high);
list.set(high, list.get(low));
list.set(low, temp);
high--;
} else{ // the value is smaller than the pivot, skip
low++;
}
}
if (list.get(low) > pivot)
low--;
// the low pointer is on the end of the first k elements
if (k <= low)
end = low;
else
start = low + 1;
}
return list.get(k);
}
};
http://lintcode.com/en/problem/kth-largest-element/ | y****9
发帖数: 252 | 2 我能想到的2nd largest 是 n + logn - 2 次对比。 |
|
