[LeetCode] 215. Kth Largest Element in an Array

轉自 LeetCode

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.

For example,
Given [3,2,1,5,6,4] and k = 2, return 5.

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

<Solution>

最簡單的做法，就是先 sort，然後從後面找第K個就可以了

原本以為這樣不會過，但看起來時間還可以

code 如下
c++

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

view raw kthLargestValueInArray_1.cpp hosted with ❤ by GitHub

kotlin

	class Solution {
	fun findKthLargest(nums: IntArray, k: Int): Int {
	return nums.sortedDescending().take(k).last()
	}
	}

view raw kth_largest_element_in_an_array.kt hosted with ❤ by GitHub

解法二

要找最大的數，就會想到用 max heap

題目說要第K大的，就 pop 掉前面 k-1 個

時間來說，比 sort 慢一點，時間複雜度是 O(KlogN)

code 如下
c++

	class Solution {
	public:
	int findKthLargest(vector<int>& nums, int k) {
	//> default will be max heap
	make_heap(nums.begin(), nums.end());
	for(int i = 0; i < k-1; i++) {
	pop_heap(nums.begin(), nums.end());
	nums.pop_back();
	}
	return nums.front();
	}
	};

view raw kthLargetValueInArray_2.cpp hosted with ❤ by GitHub

kotlin

	class Solution {
	fun findKthLargest(nums: IntArray, k: Int): Int {
	val pq = PriorityQueue { v1: Int, v2: Int -> v2 - v1 } //max heap
	for(n in nums) {
	pq.add(n)
	}
	IntRange(1,k-1).forEach {
	pq.remove()
	}
	return pq.first()
	}
	}

view raw kth_largest_element_in_an_array.kt hosted with ❤ by GitHub