讨论/《数组类算法》 - 数组中的第K个最大元素 - 解题思路/
《数组类算法》 - 数组中的第K个最大元素 - 解题思路
共 2 个回复
class Solution {
    public int findKthLargest(int[] nums, int k) {
        return selection(nums, 0, nums.length - 1, nums.length - k);
    }

     private int selection(int[] nums, int l, int r, int c) {
         int q = partion(nums, l, r);
         if (q == c) {
             return nums[q];
         } else {
             return q < c ? selection(nums, q + 1, r, c) : selection(nums, l, q - 1, c);
         }
     }

     private int partion(int[] arr, int l, int r) {
         int pivot = arr[l];
         int sp = l + 1;
         int bigger = r;
         while (sp <= bigger) {
             if (arr[sp] <= pivot) {
                 sp++;
             } else {
                 swap(arr, sp, bigger);
                 bigger--;
             }
         }
         swap(arr, l, bigger);
         return bigger;

     }
     private void swap(int[] arr, int sp, int bigger) {
         int temp = arr[sp];
         arr[sp] = arr[bigger];
         arr[bigger] = temp;
     }
 }

class Solution {
public int findKthLargest(int[] nums, int k) {
int temp = 0;
for(int i=0; i<nums.length-1;i++) {
for (int j=i+1;j<nums.length;j++) {
if (nums[i] < nums[j]) {
temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
}
int count = 1;
int p = 0;
for (int l = 0; l<nums.length;l++) {
if (nums[l] != nums[0]) {
count++;
}
if (count == k) {
p = l;
break;
}
}
return nums[p];

}

}