【每日一题】【找到位置返回&升序数组中第K大就是n-K小】2022年1月17日-NC88 寻找第K大

描述
有一个整数数组，请你根据快速排序的思路，找出数组中第 k 大的数。

给定一个整数数组 a ,同时给定它的大小n和要找的 k ，请返回第 k 大的数(包括重复的元素，不用去重)，保证答案存在。

方法：快速排序+找到位置就返回

import java.util.*;

public class Solution {

    public int findKth(int[] a, int n, int K) {

        //第k大就是n-k小

        quickSort(a, 0, n - 1, n - K);

        return a[n - K];

    }

    public void quickSort(int[] a, int low, int high, int K) {

        if(low >= high) return;

        int i = low, j = high;

        int pivot = a[low];

        while(i < j) {

            while(i < j && a[j] > pivot) {

                j--;

            }

            if(i < j) {

                a[i++] = a[j];

            }

            while(i < j && a[i] < pivot) {

                i++;

            }

            if(i < j) {

                a[j--] = a[i];

            }

        }

        a[i] = pivot;

        //第i就是K的位置，表示找到了最终位置，即可返回

        if(K == i) {

            return;

        }

        quickSort(a, low, i - 1, K);

        quickSort(a, i + 1, high, K);

    }

}

【每日一题】【找到位置返回&升序数组中第K大就是n-K小】2022年1月17日-NC88 寻找第K大的相关教程结束。