寻找第K大的数

101 阅读 0 评论 67 点赞

我是靠谱客的博主纯情绿茶，这篇文章主要介绍寻找第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);
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
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);
        }
    }
}