领扣LintCode问题答案-5. 第k大元素

5. 第k大元素

在数组中找到第 k 大的元素。
你可以交换数组中的元素的位置

样例 1：

输入：
n = 1, nums = [1,3,4,2]
输出：
4

样例 2：

输入：
n = 3, nums = [9,3,2,4,8]
输出：
4

public class Solution {
/**
	 * @param n: An integer
	 * @param nums: An array
	 * @return: the Kth largest element
	 */
	public int kthLargestElement(int n, int[] nums) {
		// write your code here
		int needIndex = nums.length - n;
		int lo = 0;
		int hi = nums.length - 1;
		int index = -1;
		while (index != needIndex) {
			index = this.partition(nums, lo, hi);
			if (index < needIndex) {
				lo = index + 1;
			} else if (index > needIndex) {
				hi = index - 1;
			}
		}

		return nums[index];
	}

	private int partition(int[] array, int lo, int hi) {
		int key = array[lo];
		while (lo < hi) {
			while (array[hi] >= key && hi > lo) {
				hi--;
			}
			array[lo] = array[hi];
			while (array[lo] <= key && hi > lo) {
				lo++;
			}
			array[hi] = array[lo];
		}
		array[hi] = key;
		return hi;
	}
}

原题链接点这里

鸣谢

非常感谢你愿意花时间阅读本文章，本人水平有限，如果有什么说的不对的地方，请指正。
欢迎各位留言讨论，希望小伙伴们都能每天进步一点点。

最后

以上就是听话发卡为你收集整理的领扣LintCode问题答案-5. 第k大元素5. 第k大元素鸣谢的全部内容，希望文章能够帮你解决领扣LintCode问题答案-5. 第k大元素5. 第k大元素鸣谢所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。