215. 数组中的第K个最大元素

// LeetCode指定调用方法
public int findKthLargest(int[] nums, int k) {
    Arrays.sort(nums);
    return nums[nums.length - k];
}

// LeetCode指定调用方法
public int findKthLargest(int[] nums, int k) {
    int len = nums.length;
    createBigHeap(nums, len);

    // 通过大顶堆排序，找出第 k个最大的元素
    for (int i = 1; i <= k; i++) {
        int temp = nums[len - i];
        nums[len - i] = nums[0];
        nums[0] = temp;
        adjustBigHeap(nums, 0, len - i);
    }

    return nums[len - k];
}

// 创建大顶堆
public void createBigHeap(int[] nums, int len) {
    for (int i = len / 2 - 1; i >= 0; i--) {
        //从第一个非叶子结点从下至上，从右至左调整结构
        adjustBigHeap(nums, i, len);
    }
}

// 调整大顶堆
public void adjustBigHeap(int[] nums, int i, int len) {
    int temp = nums[i];
    for(int j = i * 2 + 1; j < len; j = j * 2 + 1){ // 遍历从i开始的左子节点，左子节点的左子节点
        if(j + 1 < len && nums[j] < nums[j + 1]){ // 如果左子结点小于右子结点，则将子节点指针j指向右子结点
            j++;
        }
        if(nums[j] > temp){ // 如果子节点大于父节点，将子节点值赋给父节点，并将父节点指针i指向该子节点
            nums[i] = nums[j];
            i = j;
        }else{
            break;
        }
    }
    nums[i] = temp;
}

// LeetCode指定调用方法
public int findKthLargest(int[] nums, int k) {

    int len = nums.length;
    int low = 0;
    int high = len - 1;

    // 将第 k个最大的元素的下标赋值给k（从小到大排序）
    k = len - k;
    // 枢轴位置
    int pos;

    // 结合题目需求，优化后的快速排序
    while (low < high) {
        pos = partition(nums, low, high);
        if (pos == k) {
            break;
        } else  if (pos > k) {
            high = pos - 1;
        } else {
            low = pos + 1;
        }
    }
    return nums[k];
}

// 进行一次快速排序，确定枢轴位置
public int partition(int[] nums, int low, int high) {

    // 通过随机数确定枢轴，降低有序数据对快速排序的影响
    Random random = new Random();
    int random_index = low + random.nextInt(high - low); 
    // 枢轴
    int temp = nums[random_index];
    nums[random_index] = nums[low];
    nums[low] = temp;
    while (low < high) {
        while (low < high && nums[high] >= temp) { // 从右往左找小于枢轴的元素
            high--;
        }
        nums[low] = nums[high];
        while (low < high && nums[low] <= temp) { // 从左往右找大于枢轴的元素
            low++;
        }
        nums[high] = nums[low];
    }
    nums[low] = temp;
    return low; // 返回枢轴位置
}