leetcode215:数组中的第K个最大元素

package com.mxnet;

import java.util.Random;

public class Solution215 {
    //生成随机数
    Random random = new Random();
    /**
     * 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
     * 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
     *
     * 你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
     * @param nums
     * @param k
     * @return
     * 思路：
     * 1. 使用快速排序的扩展方法 快速查找思路
     * 2. 随机选择数组中一个元素，然后将数组中其他元素分为比它小和比它大两部分
     * 3. 选择第K大元素实质为选择数组元素排好序后的第 len - K个元素
     * 4. 通过判断所选择元素和 目标元素的关系，逐渐缩小查找范围
     *
     */
    public int findKthLargest(int[] nums, int k) {
        //第k大数所在数组中的索引位置
        int target = nums.length - k;
        //数组左索引
        int left = 0;
        //数组右索引
        int right = nums.length - 1;
        //重复找第K大数，直到找到为止
        while (true){
            //使用快速查找思路随机找出一个值并记录其索引位置
            int pivotIndex = partition(nums, left, right);
            //如果找到的索引值和目标值一样，返回即可
            if (target == pivotIndex){
                return nums[pivotIndex];
                //若查找到的值小于目标值，改变边界条件，继续查找
            }else if (target > pivotIndex){
                left = pivotIndex + 1;
                //若大于，同样继续查找
            }else {
                right = pivotIndex - 1;
            }
        }
    }

    /**
     * 将数组中的元素以pivot元素分隔开，使得其前边元素小于它，后边元素大于它
     * @param nums
     * @param left
     * @param right
     * @return
     */
    public int partition(int[] nums, int left, int right){
        //随机寻找一个数作为pivot,以这个数为中心将所有元素分为左右两端
        int pivotIndex = left + random.nextInt(right - left + 1);
        //将该数放到数组第一个元素
        swap(nums,left,pivotIndex);
        //记录剩余数字索引
        int l = left + 1;
        int r = right;
        //循环执行 将大于该数和小于该数的元素分开
        while (true){
            //若元素小于该数，不用处理
            while (l <= r && nums[l] <= nums[left]){
                l++;
            }
            //若大于该数，不用处理
            while (l <= r && nums[r] >= nums[left]){
                r--;
            }
            //循环结束条件，扫描完所有元素
            if (l >= r){
                break;
            }
            //当左右两侧元素都不满足时交换
            swap(nums,l,r);
            l++;
            r--;
        }
        //最后保存pivot元素的索引位置
        swap(nums, left, r);
        return r;
    }

    //交换数组中两个元素的位置
    public void swap(int[] nums, int index1, int index2){
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}