kth-largest-element
2024-08-22 12:28:39
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.
思路：
1.利用快速排序partition的思想
2.partition函数返回pivot的下标, 位于pivot左边的数都小于等于pivot,位于pivote右边的数都大于等于pivote.
3.当pivote + 1 == nums.length - k + 1 时，表明 nums[pivote] 为 从大到小的第K个的数
当 pivote + 1 < nums.length - k + 1 时， 表明 第k大的数在pivote 的右边
当 pivote + 1 > nums.length - k + 1 时，表明第K大的书在pivote的左边
class Solution {
/*
* @param k : description of k
* @param nums : array of nums
* @return: description of return
*/
public int kthLargestElement(int k, int[] nums) {
// write your code here
if (nums == null || nums.length == 0) {
return 0;
}
if (k <= 0) {
return 0;
}
return helper(nums, 0, nums.length - 1, nums.length - k + 1);
}
/*
K 为小于等于第K大的数的个数
*/
public int helper(int[] nums, int l, int r, int k) {
if (l == r) {
return nums[l];
}
int position = partition(nums, l, r);
if (position + 1 == k) {
return nums[position];
} else if (position + 1 < k) {
return helper(nums, position + 1, r, k);
} else {
return helper(nums, l, position - 1, k);
}
}
public int partition(int[] nums, int l, int r) {
if (l == r) {
return l;
}
int left = l, right = r;
int now = nums[left];
while (left < right) {
while (left < right && nums[right] >= now) {
right--;
}
nums[left] = nums[right];
while (left < right && nums[left] <= now) {
left++;
}
nums[right] = nums[left];
}
nums[left] = now;
return left;
}
};
最新文章
- 一些VS2013下使用QT和MFC的错误解决方案
- C/C++语言，自学资源，滚动更新中……
- jquery实现css3动画
- Access数据库的模糊查询到底是用*还是%
- 使用Diagnose服务查看Azure网站诊断信息
- 图片button
- chrome浏览器关闭标签页面
- hadoop 常见问题
- 条件与（&&）和逻辑与（&）以及条件或（||）和逻辑或（|）区别
- SparkContext自定义扩展textFiles，支持从多个目录中输入文本文件
- jquery-multiselect在ie6里的一个bug
- A fatal error has been detected by the Java Runtime Environment:
- Portal.MVC
- 学习《ASP.NET MVC5高级编程》——基架
- iOS 动态 Framework 对App启动时间影响实测
- div宽高不确定，内容居中
- spring quartz整合实现定时器自动注解
- 同时安装anaconda2和anaconda3
- 雷林鹏分享：jQuery EasyUI 窗口 - 自定义窗口工具栏
- 将mongo设置为windows的服务