本文准备讲解1个算法编程问题, 这个算法编程问题来自LeetCode平台和LintCode平台。不了解.LeetCode平台的读者可以阅读笔者文章(在线编程平台推荐-LeetCode)。问题的英文版本描述如下:
Find K-th largest element in an array.
Example
In array[9,3,2,4,8], the second largest element is 8.
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.
问题的中文版本描述:
在数组中找到第k大的元素:
样例
给出数组[9,3,2,4,8],第二大的元素是8
给出数组[1,2,3,4,5],第一大的元素是5,第二大的元素是4,第三大的元素是3,以此类推
该问题的完全解法需要用到 Quick Sort 算法,该算法的最佳图解来自于 algorithm in a nutshell。请参见下图:
对应完全算法的代码如下:
曾经发现多个该解法的变化版本,有的版本很难阅读,有的版本表现更好。但本文仍然推荐以上的代码方案,因为该方案与 Quick Sort 算法本身高度匹配。最后,公布1种较好的算法处理方案;这种方案在 LeetCode /LintCode 平台上需要更短 的程序运行时间且只含2句代码。代码为:
Arrays.sort(nums);
return nums[nums.length - k];