LeetCode: Kth Largest Element in an Array (sorting)
https://leetcode.com/problems/kth-largest-element-in-an-array/, problem statement:
public class Solution
{
public int FindKthLargest(int[] nums, int k)
{
Array.Sort(nums);
return nums[nums.Length - k];
}
}
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
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.
Two-lines solution: sort & index. Code's below, cheers, Marcelo.You may assume k is always valid, 1 ≤ k ≤ array's length.
{
public int FindKthLargest(int[] nums, int k)
{
Array.Sort(nums);
return nums[nums.Length - k];
}
}
Haha, I can only imagine what were solutions which took >600ms doing :) Technically sorting an entire array is not necessary and a simple algorithm based on a quick sort partitioning is usually faster - it takes only 9ms in C++ and beats ~92% of other solutions. FYI, C++ also has a way to cheat - nth_element:
ReplyDeleteint findKthLargest(const vector& nums, int k) {
nth_element(nums.begin(), nums.end() - k, nums.end());
return nums[nums.size()-k];
}
Thanks for sharing!
Ha, didn't know about the nth_element function, it was like it was meant to solve this problem! :)
Deletethere are lots of hidden gems in C++'s standard library :)
DeleteThanks for sharing this blog its very informative and useful for us.
ReplyDeleteซอมบี้