class Solution {
int quickselect(int[] nums, int l, int r, int k) {
if (l == r) return nums[k];
int x = nums[l], i = l - 1, j = r + 1;
while (i < j) {
do i++; while (nums[i] < x);
do j--; while (nums[j] > x);
if (i < j){
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
//一次比较完之后，i=j,j右边都是大于x的，j左边的都是小于x的
//判断递归范围
if (k <= j) return quickselect(nums, l, j, k);
else return quickselect(nums, j + 1, r, k);
}
public int findKthLargest(int[] _nums, int k) {
int n = _nums.length;
return quickselect(_nums, 0, n - 1, n - k);
}
}
解法3.基于堆排序的选择方法
class Solution {
public int findKthLargest(int[] nums, int k) {
int heapSize = nums.length;
buildMaxHeap(nums, heapSize);
for (int i = nums.length - 1; i >= nums.length - k + 1; --i) {
swap(nums, 0, i);
--heapSize;
maxHeapify(nums, 0, heapSize);
}
return nums[0];
}
public void buildMaxHeap(int[] a, int heapSize) {
for (int i = heapSize / 2; i >= 0; --i) {
maxHeapify(a, i, heapSize);
}
}
public void maxHeapify(int[] a, int i, int heapSize) {
int l = i * 2 + 1, r = i * 2 + 2, largest = i;
if (l < heapSize && a[l] > a[largest]) {
largest = l;
}
if (r < heapSize && a[r] > a[largest]) {
largest = r;
}
if (largest != i) {
swap(a, i, largest);
maxHeapify(a, largest, heapSize);
}
}
public void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
解法：首先将项目按照所需资本的从小到大进行排序，每次进行选择时，假设当前手中持有的资本为 w，我们应该从所有投入资本小于等于 w 的项目中选择利润最大的项目 j，然后此时我们更新手中持有的资本为 w+profits[j]，同时再从所有花费资本小于等于 w+profits[j]的项目中选择，我们按照上述规则不断选择 k 次即可。
先把所有满足<=w的项目都入堆，在堆里面按利润从大到小排序，然后出堆。
class Solution {
public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
int n = profits.length;
int curr = 0;
int[][] arr = new int[n][2];
for (int i = 0; i < n; ++i) {
arr[i][0] = capital[i];
arr[i][1] = profits[i];
}
//按资本从小到大排列
Arrays.sort(arr, (a, b) -> a[0] - b[0]);
//按利润的降序排列
PriorityQueue<Integer> pq = new PriorityQueue<>((x, y) -> y - x);
//选择K个项目
for(int i=0; i< k; i++){
//总共n个项目，选择满足小于起始金额的项目，并入堆。
while(curr < n && arr[curr][0] <=w){
pq.add(arr[curr][1]);
curr++;
}
//挑选一个利润最大的项目，出堆。
if(!pq.isEmpty()){
w+=pq.poll();
}else{
break;
}
}
return w;
}
}