寻找第K大的数

题目

有一个整数数组，请你根据快速排序的思路，找出数组中第K大的数。
给定一个整数数组a,同时给定它的大小n和要找的K(K在1到n之间)，请返回第K大的数，保证答案存在。

分析

有个细节需要注意，题目是寻找第K大的数，是数组排序后从后往前数的第K个数，而不是从前往后数第K个数，当然这题最后要转化一下，第K大的数对应的是数组中第（n-K+1）小的数，因此我们只需要找到数组中第（n-K+1）小的数即可。
快排的思想：我们知道根据快速排序，每次能确定一个被当成中间枢纽的数povit的位置position，因此我们可以确定position与(n-K+1)的大小，如果他们相等，那么povit就是第(n-K+1)个小的数，如果(n-K+1)>position,我们只需要在后面一段找到第(n-K+1)-position个小的数即可，如果(n-K+1)<position,那么我们需要在前面一段找到第(n-K+1)小的数，具体看下面的代码：

import java.util.*;

public class Solution {
    public int findKth(int[] a, int n, int K) {
       return quickSort(a,0,n-1,n-K+1);
    }
    public int quickSort(int[] arr,int begin,int end,int k) {
        //中间枢纽
        int povit = arr[begin];
        int left = begin;
        int right = end;
        while(left < right) {
            //找比povit大的数
            if(arr[left] < povit) {
                left++;
                continue;
            }
            if(arr[right] > povit) {
                right--;
                continue;
            }
            //交换两者的位置
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            //这一步很重要，如果没有可能会陷入死循环（left和right指向的值相等时）
            if(arr[left] == povit) {
                right--;
            } else {
                left++;
            }
        }
        int len = left-begin+1;
        if(len == k) {
            return arr[left];
        } else if(len < k) {
            return quickSort(arr,left+1,end,k-len);
        } else {
            return quickSort(arr,begin,left-1,k);
        }
    }
}

如果对快速排序不熟悉，可以看看这篇文章，九大排序算法里面有详细的排序算法的过程。

时间复杂度：o(nlgn)

最后

以上就是纯情绿茶为你收集整理的寻找第K大的数的全部内容，希望文章能够帮你解决寻找第K大的数所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。