前言
1.(Math.random()(x-y))+y // Math.random()(x-y+1)+y; 随机数x~y
2.递归
3.三目运算法则
4.快排模板
void quick_sort(int q[], int l, int r) { if (l >= r) return; int i = l - 1, j = r + 1, x = q[l + r >> 1]; while (i < j) { do i ++ ; while (q[i] < x); do j -- ; while (q[j] > x); if (i < j) swap(q[i], q[j]); } quick_sort(q, l, j), quick_sort(q, j + 1, r); } 作者：yxc 链接：https://www.acwing.com/blog/content/277/ 来源：AcWing
一、题目描述
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
提示：
1 <= k <= nums.length <= 104
-104 <= nums[i] <= 104
二、思路
目标寻找第k大的数，所以可以利用快排(快排基础就不细说了，可以自己去了解一下)，这些数不一定排好，标准数左边是大数，右边是小数，然后再在左边大数中寻找目标数，如果此时标准数刚刚好是所求下标(在数组中是k-1)，则即为所求值。
三、代码实现
代码如下（示例）：
class Solution { public int findKthLargest(int[] nums, int k) { return QuickSort(nums,0,nums.length-1,k); } public int QuickSort(int nums[],int l,int r,int k) { int index = randomParam(nums, l, r); if(index == k-1) { return nums[index]; }else{ return index>k-1? QuickSort(nums,l,index-1,k): QuickSort(nums,index+1,r,k); } } public int randomParam(int nums[],int l,int r) { int b = (int)(Math.random()*(r-l+1)+l); swap(nums,b,r); return quick_sort(nums,l,r); } public int quick_sort(int nums[],int l,int r) { // 可以记住这个模板，把基准数默认放到最右边，然后开始左右指针移动比较 //这里没有用那个do_while模板，那个容易超过时间限制 int c = r; int index = nums[r]; while(l<r) { while(l<r && nums[l] > index) l++; while(l<r && nums[r] <= index) r--; if(l<r) swap(nums,l,r); } swap(nums,l,c); return l; } public void swap(int [] nums,int l, int r) { int temp = nums[l]; nums[l] = nums[r]; nums[r] = temp; } }
