寻找数组中第K大的数

剑指offer——寻找数组中的第 K 大的数

题目描述

给定一个数组A，要求找到数组A中第K大的数字。

思路：对于这种题目，其实有多种解法

方法1：对数组A进行排序，然后遍历一遍就可以找到第K大的数字。该方法的时间复杂度为O(N*logN)

方法2：利用简单选择排序法的思想，每次通过比较选出最大的数字来，比较上K次就能找出第K大的数字来。该方法的时间复杂度为O(N*K)，最坏情况下为O(N^2)。

方法3：也是本文介绍的最重要的一种方法。利用快速排序算法 partition 的思想来解决。首先快排每次执行都能确定一个元素的最终的位置，如果这个位置是n-k(其中n是数组A的长度)的话，那么就相当于找到了第K大的元素。设确定的元素位置m的话，如果m 在 n-k 的右边的话，即 m > n - k，那么第K大的数字一定在m的左边，即A[0]~A[m - 1]之间；如果m在 n-k 的左边的话，即 m < n - k，那么第K大的数字一定在m的右边，即A[m+1]~A[n - 1]之间。整个过程可以通过递归实现，具体代码如下：

public int KthElement(int[] arr, int k){
    int n = arr.length;
    if(arr == null || k > n)
        return 0;
    
    int start = 0;
    int end = n - 1;
    int index = partition(arr,start,end);
    while(index != n - k){
        if(index < (n-k)){ //在该元素的右边继续寻找
            start = index + 1; 
            index = partition(arr,start,end);
        }
        if(index > (n-k)){//在该元素的左边继续寻找
            end = index - 1;
            index = partition(arr,start,end);
        }
        
    }
    return arr[index];
}

public int partition(int[] arr, int start, int end){
    int i = start;
    int j = end;
    int key = arr[i];
    while(i < j){
        while(i < j && arr[j] >= key){
            j--;
        }
        arr[i] = arr[j];
        i++;
        while(i < j && arr[i] <= key){
            i++;
        }
        arr[j] = arr[i];
        j--;
    }
    arr[i] = key;
    return i;
}

特别注意：

1.第K大的数字在数组中对应的位置为n-k(按照升序排序的话)。

2.该算法的时间复杂度整体上为O(N)。

3.需要注意的是：这种方法会改变数组中元素的顺序，即会改变数组本身。

4.如果要求第K小的数字的话，只需把n-k换成k-1即可(升序排序)。