# [LeetCode] 215. Kth Largest Element in an Array 数组中第k大的元素

2018/03/06 16:01

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example 1:

```Input: `[3,2,1,5,6,4] `and k = 2
Output: 5
```

Example 2:

```Input: `[3,2,3,1,2,4,5,5,6] `and k = 4
Output: 4```

Note:
You may assume k is always valid, 1 ≤ k ≤ array's length.

Java: Sort, T: O(nlogn) S: O(1)

``````public class Solution {
public int findKthLargest(int[] nums, int k) {
Arrays.sort(nums);
return nums[nums.length - k];
}
}``````

Java: MaxHeap, T: O(nlogk) S: O(k)

``````public class Solution {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> p = new PriorityQueue<Integer>();
for(int i = 0 ; i < nums.length; i++){
if(p.size()>k) p.poll();
}
return p.poll();
}
}``````

Java: Quick select, T: Avg O(n) Worst O(n^2), S: O(1)

``````public class Solution {
public int findKthLargest(int[] nums, int k) {
return quickSelect(nums, k - 1, 0, nums.length - 1);
}

private int quickSelect(int[] arr, int k, int left, int right){
int pivot = arr[(left + right) / 2];
int orgL = left, orgR = right;
while(left <= right){
// 从右向左找到第一个小于枢纽值的数
while(arr[left] > pivot){
left ++;
}
// 从左向右找到第一个大于枢纽值的数
while(arr[right] < pivot){
right --;
}
// 将两个数互换
if(left <= right){
swap(arr, left, right);
left ++;
right --;
}
}
// 最后退出的情况应该是右指针在左指针左边一格
// 这时如果右指针还大于等于k，说明kth在左半边
if(orgL < right && k <= right) return quickSelect(arr, k, orgL, right);
// 这时如果左指针还小于等于k，说明kth在右半边
if(left < orgR && k >= left) return quickSelect(arr, k, left, orgR);
return arr[k];

}

private void swap(int[] arr, int idx1, int idx2){
int tmp = arr[idx1] + arr[idx2];
arr[idx1] = tmp - arr[idx1];
arr[idx2] = tmp - arr[idx2];

}
}　``````

Python: Sort

``````class Solution:
# @param {integer[]} nums
# @param {integer} k
# @return {integer}
def findKthLargest(self, nums, k):
return sorted(nums, reverse=True)[k - 1]``````

Python: Max Heap

``````from heapq import *
class Solution(object):
def findKthLargest(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
if not nums:
return -1

h = []
for i in xrange(len(nums)):
if len(h) < k:
heappush(h, nums[i])
else:
if h[0] < nums[i]:
heappop(h)
heappush(h, nums[i])

return h[0]``````

Python: Quick select

``````import random
class Solution:
def findKthLargest(self, nums, k):
pivot = random.choice(nums)
nums1, nums2 = [], []
for num in nums:
if num > pivot:
nums1.append(num)
elif num < pivot:
nums2.append(num)
if k <= len(nums1):
return self.findKthLargest(nums1, k)
if k > len(nums) - len(nums2):
return self.findKthLargest(nums2, k - (len(nums) - len(nums2)))
return pivot``````

Python: Quick select

``````class Solution:
# @param {integer[]} nums
# @param {integer} k
# @return {integer}
def findKthLargest(self, nums, k):
left, right = 0, len(nums) - 1
while left <= right:
pivot_idx = randint(left, right)
new_pivot_idx = self.PartitionAroundPivot(left, right, pivot_idx, nums)
if new_pivot_idx == k - 1:
return nums[new_pivot_idx]
elif new_pivot_idx > k - 1:
right = new_pivot_idx - 1
else:  # new_pivot_idx < k - 1.
left = new_pivot_idx + 1

def PartitionAroundPivot(self, left, right, pivot_idx, nums):
pivot_value = nums[pivot_idx]
new_pivot_idx = left
nums[pivot_idx], nums[right] = nums[right], nums[pivot_idx]
for i in xrange(left, right):
if nums[i] > pivot_value:
nums[i], nums[new_pivot_idx] = nums[new_pivot_idx], nums[i]
new_pivot_idx += 1

nums[right], nums[new_pivot_idx] = nums[new_pivot_idx], nums[right]
return new_pivot_idx``````

C++: Sort

``````class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
return nums[nums.size() - k];
}
};``````

C++: Priority queque

``````class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
/** priority_queue<int, vector<int>, less<int>> q; **/
priority_queue<int, vector<int>> q;
int len=nums.size();
for(int val:nums){
q.push(val);
}
while(q.size() > len-k+1){
q.pop();
}
return q.top();
}
};``````

C++: MaxHeap

``````class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
//max heap method
//min heap method
//order statistics
make_heap(nums.begin(), nums.end());
int result;
for(int i=0; i<k; i++){
result=nums.front();
pop_heap(nums.begin(), nums.end());
nums.pop_back();
}
return result;
}
};``````

C++: Quick sort, partition

``````class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
int high = nums.size();
int low = 0;
while (low < high) {
int i = low;
int j = high-1;
int pivot = nums[low];
while (i <= j) {
while (i <= j && nums[i] >= pivot)
i++;
while (i <= j && nums[j] < pivot)
j--;
if (i < j)
swap(nums[i++],nums[j--]);
}
swap(nums[low],nums[j]);

if (j == k-1)
return nums[j];
else if (j < k-1)
low = j+1;
else
high = j;
}
}
};``````

0
0 收藏

0 评论
0 收藏
0