第k大的数

快速排序与查找第K大的数
千次阅读
2019-09-11 23:59:32
快速排序与查找第K大的数

今天种树的任务是复习一下快排，顺便实现了一下查找第K大的数的算法。

快速排序

非常常见也非常经典的算法，随便给你们找一篇。
https://www.cnblogs.com/ayqy/p/3862938.html

快速排序C++实现

我觉得我写的又短又好理解又好记忆（自恋ing~）
```
#include <iostream>
#include <stack>
#include <time.h>
#include <stdlib.h>
using namespace std;

int arrs[] = { 23, 476, 65, 12, 3, 925, 8, 98, 76, 345, 90, 21, 762, 75, 34, 123, 61 };
int length = sizeof(arrs) / sizeof(arrs[0]);

void QuickSort(int* istart,int* iend)
{
    int* left = istart;
    int* right = iend;
    while(left != right)
    {
        while(*left <= *right && left < right)
            right--;
        swap(*left, *right);
        while(*left <= *right && left < right)
            left++;
        swap(*left, *right);
    }
    if (left > istart)
        QuickSort(istart, left - 1);
    if (left < iend)
        QuickSort(left + 1, iend);
}

int main()
{
    QuickSort(arrs, arrs + length - 1);
    for(int i = 0;i<length;i++)
        cout<<arrs[i]<<" ";
    return 0;
}
```
查找第K大的数

今天看书说快排可以实现查找第K大的数，突然觉得很牛b。赶紧来试试。贴两篇博文
https://www.cnblogs.com/zhjp11/archive/2010/02/26/1674227.html（摘要如下）

所谓“第（前）k大数问题”指的是在长度为n(n>=k)的乱序数组中S找出从大到小顺序的第（前）k个数的问题。
解法1：我们可以对这个乱序数组按照从大到小先行排序，然后取出前k大，总的时间复杂度为O(nlogn + k)。
解法2：利用选择排序或交互排序，K次选择后即可得到第k大的数。总的时间复杂度为O(nk)
解法3：利用快速排序的思想，从数组S中随机找出一个元素X，把数组分为两部分Sa和Sb。Sa中的元素大于等于X，Sb中元素小于X。这时有两种情况：
1. Sa中元素的个数小于k，则Sb中的第k-|Sa|个元素即为第k大数；
2. Sa中元素的个数大于等于k，则返回Sa中的第k大数。时间复杂度近似为O(n)
解法4：二分[Smin,Smax]查找结果X，统计X在数组中出现，且整个数组中比X大的数目为k-1的数即为第k大数。时间复杂度平均情况为O(nlogn)
解法5：用O(4n)的方法对原数组建最大堆，然后pop出k次即可。时间复杂度为O(4n + klogn)
解法6：维护一个k大小的最小堆，对于数组中的每一个元素判断与堆顶的大小，若堆顶较大，则不管，否则，弹出堆顶，将当前值插入到堆中。时间复杂度O(n * logk)
解法7：利用hash保存数组中元素Si出现的次数，利用计数排序的思想，线性从大到小扫描过程中，前面有k-1个数则为第k大数，平均情况下时间复杂度O(n)

作者给出7种方法，并计算其时间复杂度。明显看到第3种快排和第7种计数排序的时间复杂度”较低“。
对于快排，平均情况应该是每次舍去一半的数组，所以时间复杂度应该是n+n/2+n/4+n/8…也就是O(2n)。
而所谓的第7种方法选择排序，时间复杂度为O(N+M)，M为数组元素的取值范围，对于通常情况下这并不是一个解决第K大问题的好方法。
再来一篇博文
https://blog.csdn.net/apolo_/article/details/50829683
解决思路是从始至终只对最大的K个数进行排序，与全排序相比，减少了很多无用操作。

第二种解法是先把前k个元素读入到数组并对齐排序（递减的循序），接着将剩下的元素在逐个读入。最后在遍历完数组后直接输出第k个元素。

这算法依赖于K的大小，当k很小时，性能优于快排。当你不知道K的取值范围时，快排是更好的选择。

快排思想实现查找第K大的数

利用快速排序的思想，从数组S中随机找出一个元素X，把数组分为两部分Sa和Sb。Sa中的元素大于X，Sb中元素小于X。这时有三种情况：
1. Sa中元素的个数小于k，则Sb中的第k-|Sa|个元素即为第k大数；
2. Sa中元素的个数大于k，则返回Sa中的第k大数。时间复杂度近似为O(n)
3. X排序等于K，返回X

C++实现

只需要在上面快排的算法上做一点小小的改动
```
#include <iostream>
#include <stack>
#include <time.h>
#include <stdlib.h>
using namespace std;

int arrs[] = { 23, 476, 65, 12, 3, 925, 8, 98, 76, 345, 90, 21, 762, 75, 34, 123, 61 };
int length = sizeof(arrs) / sizeof(arrs[0]);

int TopKSort(int* istart,int* iend, int k)
{
    int* left = istart;
    int* right = iend;
    while(left != right)
    {
        while(*left >= *right && left < right)
            right--;
        swap(*left, *right);
        while(*left >= *right && left < right)
            left++;
        swap(*left, *right);
    }
    if (left - istart + 1 == k)
        return *left;
    if (left - istart + 1 > k)
        return TopKSort(istart, left - 1, k);
    if (left - istart + 1 < k)
        return TopKSort(left + 1, iend, k - (left - istart + 1));
}

int main()
{
    for(int i = 0;i<length;i++)
        cout<<TopKSort(arrs, arrs + length - 1, i + 1)<<" ";
    return 0;
}
```
运行结果：

925 762 476 345 123 98 90 76 75 65 61 34 23 21 12 8 3

学算法有瘾，为什么我以前没发现这么快乐的事情呢❓呜呜，种树+4
快速排序

更多相关内容
查找数组中第k大的数
2016-01-08 16:22:07

给定一数组，查找数组中第k大的数。代码中借助快速排序中的partition方法来实现。

收起
C++——寻找第k大的数
2021-05-24 18:39:33
给出一个数组，找出数组的第k大的数：基于快速排序的思路，每次快排后，基准的左边都是比其小的数，右边都是比其大的数，一次快排结束后，若基准所处的位置正好是第k大（即基准右边有k-1个数据），则返回基准值。...
给出一个数组，找出数组的第k大的数：基于快速排序的思路，每次快排后，基准的左边都是比其小的数，右边都是比其大的数，一次快排结束后，若基准所处的位置正好是第k大（即基准右边有k-1个数据），则返回基准值。若基准所在的位置右边的数据小于k-1个，说明第k大的数在基准左边序列中，则我们需要对左边的数据进行快排，并找到第k-big-1大的数据；若基准所在的位置右边的数据大于k-1个，说明第k大的数在基准右边序列中，则对右边的序列进行快排并找到第k大的数。
```
class Solution {
public:
    int findKth(vector<int> a, int n, int K) {
        // write code here
        return quickFind(a, 0, n-1,K);
        
    }
    int quickFind(vector<int>& arr,int left,int right,int k){
        int i=left,j=right,key=arr[left];
        while(i<j){
            while(i<j&&arr[j]>=key) j--;
            arr[i]=arr[j];
            while(i<j&&arr[i]<=key) i++;
            arr[j]=arr[i];
        }
        arr[i]=key;
        int big=right-i;
        if(big==k-1) return key;
        else if(big<k-1) 
            return quickFind(arr, left, i-1,k-big-1);
        else
            return quickFind(arr,i+1, right,k);
    }
};
```
收起
展开全文
快速排序 C++
求N个数中第K大的数
2013-12-02 20:26:41

基于快排的查找来得到N个数中第K大的数，时间复杂度为O(KlogN)

收起

排序

快速排序计算第K大的数

千次阅读 2020-03-26 10:58:34

熟悉快排的同学都知道，若不熟悉的... 例如1,3,4,2这组数字，使用快排以2为基准点进行倒序排序第一次的结果为3,4,2,1 ，如果你恰好是求第3大的数，那么就是基准点2，只用了一次排序，时间复杂度为O(n)。如果你是求第...

先说结论，最终版本代码如下：

public class KthNum {
    public static int k = 2;
    public static boolean bigK = false;

    public static void main(String[] args) {
        int arr[] = {3, 2, 3, 1, 7, 4, 5, 5, 6};
        int kNum = quickSort(arr);
        System.out.println("kNum=" + kNum);
    }

    public static int quickSort(int arr[]) {
        int length = arr.length;
        if (k <= 0 || k > length) throw new RuntimeException("K值不合理");
        int left = 0, right = length - 1;
        int p = -1;
        while (k != p + 1) {
            if (k < p + 1) {
                right = p - 1;
            } else if (k > p + 1) {
                left = p + 1;
            }
            p = partition(arr, left, right);
        }
        return arr[p];
    }

    public static int partition(int[] arr, int left, int right) {
        int pivot = arr[right];
        int sortIndex = left;
        for (int arrIndex = sortIndex; arrIndex < right; arrIndex++) {
            if (bigK ? arr[arrIndex] > pivot : arr[arrIndex] < pivot) {
                swap(arr, arrIndex, sortIndex);
                sortIndex++;
            }
        }
        swap(arr, sortIndex, right);
        return sortIndex;
    }

    public static void swap(int[] arr, int i, int j) {
        if (i == j) return;
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }


}

还是老规矩，我会重点谈思路，到底是如何想出这段代码的，请往下看。

熟悉快排的同学都知道，若不熟悉的同学，可以先看我的这篇白话解析快速排序。快排使用某一个数作为基准点进行分区，通常基准点左边的数都是小于基准点的，在基准点右边的数都是大于基准点的。

例如1,3,4,2这组数字，使用快排以2为基准点进行倒序排序第一次的结果为3,4,2,1 ，如果你恰好是求第3大的数，那么就是基准点2，只用了一次排序，时间复杂度为O(n)。如果你是求第1大的数或者第2大的数，那么继续在基准点左边进行排序比较即可；如果你是求第4大的数，那么在基准点右边进行排序比较即可。细心的同学可以发现求第K大的数，K的值是和基准点的下标有关系的。第一次排序完成后，基准点2的下标为2，使用下标+1和K进行比较，若K等于下标+1直接返回当前下标的值；若K大于下标+1，则继续在基准点右边进行查找；若K小于下标+1，则继续在基准点左边进行查找。循环查找，直到K等于下标+1，则结束。

基于以上的思路和对快排的理解，我们得出了计算第K大数的第一个版本1.0。

1.0：

public class KthNum {
    public static void main(String[] args) {
        int arr[] = {3, 2, 3, 1, 7, 4, 5, 5, 6};
        int k = 2;
//        k=4;
        int kNum = quickSort(arr, 0, arr.length - 1, k);
        System.out.println("kNum=" + kNum);

    }

    public static int quickSort(int arr[], int left, int right, int k) {
        if (left >= right) return -1;
        int p = partition(arr, left, right);
        while (k != p + 1) {
            if (k < p + 1) {
                p = partition(arr, left, p - 1);
            } else if (k > p + 1) {
                p = partition(arr, p + 1, right);
            }
        }
        return arr[p];
    }

    public static int partition(int[] arr, int left, int right) {
        int pivot = arr[right];
        int sortIndex = left;
        for (int arrIndex = sortIndex; arrIndex < right; arrIndex++) {
            if (arr[arrIndex] > pivot) {
                swap(arr, arrIndex, sortIndex);
                sortIndex++;
            }
        }
        swap(arr, sortIndex, right);
        return sortIndex;
    }

    public static void swap(int[] arr, int i, int j) {
        if (i == j) return;
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

以上代码在K为2时，可以正常求出第2大的数为6,。但是当K为4时，会发生死循环。

那么为什么发生死循环:

思路1：

仔细查看while循环中 if 和 else if 中的代码，分析其执行过程如下：

上图是每一次执行完 partition 方法后，基准点的下标 p 的位置。通过分析第9次和第14次的执行结果，可以发现如果继续往下走就会进入9-13次的死循环。现在已经发现了问题，那么造成问题的原因是什么？

2个问题导致的：

1. while循环中left 和 right 的值一直没发生变化

2. 通过分析第8次的执行结果，可以发现2个相同的值5在比较时不会发生数据交换，这导致7, 6, 5, 4, 5, 3, 3, 2, 1 中的第4个数和第5个数无法形成有序的位置。

思路2：

将while循环中的代码和快排中的代码对比会发现，在循环中 left 和 right 的值一直没发生变化的。初步估计会导致已经排过序的数下次循环会继续参与排序，从而导致死循环。

1.0小结：

主要是想通过复制粘贴的方式快速实现第K大数的方案，偷懒的心态导致了此版本中的死循环问题

1.1：

··修复1.0版本中的死循环问题：

public class KthNum {
    public static void main(String[] args) {
        int arr[] = {3, 2, 3, 1, 7, 4, 5, 5, 6};
        int k = 2;
        k=4;
        int kNum = quickSort(arr, 0, arr.length - 1, k);
        System.out.println("kNum=" + kNum);

    }

    public static int quickSort(int arr[], int left, int right, int k) {
        if (left >= right) return -1;
        int p = partition(arr, left, right);
        while (k != p + 1) {
            if (k < p + 1) {
                p = partition(arr, left, p - 1);
            } else if (k > p + 1) {
                p = partition(arr, p + 1, right);
            }
        }
        return arr[p];
    }

    public static int partition(int[] arr, int left, int right) {
        int pivot = arr[right];
        int sortIndex = left;
        for (int arrIndex = sortIndex; arrIndex < right; arrIndex++) {
            if (arr[arrIndex] >= pivot) {
                swap(arr, arrIndex, sortIndex);
                sortIndex++;
            }
        }
        swap(arr, sortIndex, right);
        return sortIndex;
    }

    public static void swap(int[] arr, int i, int j) {
        if (i == j) return;
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }


}

修改了 partition 方法中第4行的代码，从 arr[arrIndex] > pivot 修改为 arr[arrIndex] >= pivot 。也就是在2个数相等时依然可以进行比较数据交换。

2.0：

··修复1.0版本中的while循环中left 和 right 的值一直没发生变化导致死循环问题，也是我们的主线版本：

public class KthNum {
    public static void main(String[] args) {
        int arr[] = {3, 2, 3, 1, 7, 4, 5, 5, 6};
        int k = 2;
        k=4;
        int kNum = quickSort(arr, 0, arr.length - 1, k);
        System.out.println("kNum=" + kNum);

    }

    public static int quickSort(int arr[], int left, int right, int k) {
        if (left >= right) return -1;
        int p = partition(arr, left, right);
        while (k != p + 1) {
            if(k<p+1){
                right=p-1;
            }else if(k>p+1){
                left=p+1;
            }
            p=partition(arr,left,right);
        }
        return arr[p];
    }

    public static int partition(int[] arr, int left, int right) {
        int pivot = arr[right];
        int sortIndex = left;
        for (int arrIndex = sortIndex; arrIndex < right; arrIndex++) {
            if (arr[arrIndex] > pivot) {
                swap(arr, arrIndex, sortIndex);
                sortIndex++;
            }
        }
        swap(arr, sortIndex, right);
        return sortIndex;
    }

    public static void swap(int[] arr, int i, int j) {
        if (i == j) return;
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }


}

修改了 quickSort 方法中第5行和第7行的代码，将while循环中的 partition 方法调用放到了 if 外面，在 if 和 else if 中修改 left 和right 的值，这样使用快排计算第K大的数就基本实现了。

3.0：

这个版本是对2.0版本的优化：

public class KthNum {
    public static void main(String[] args) {
        int arr[] = {3, 2, 3, 1, 7, 4, 5, 5, 6};
        int k = 2;
        k=4;
        int kNum = quickSort(arr, 0, arr.length - 1, k);
        System.out.println("kNum=" + kNum);
    }

    public static int quickSort(int arr[], int left, int right, int k) {
        if (left >= right) return -1;
        int p=-1;
        while (k != p + 1) {
            if(k<p+1){
                right=p-1;
            }else if(k>p+1){
                left=p+1;
            }
            p=partition(arr,left,right);
        }
        return arr[p];
    }

    public static int partition(int[] arr, int left, int right) {
        int pivot = arr[right];
        int sortIndex = left;
        for (int arrIndex = sortIndex; arrIndex < right; arrIndex++) {
            if (arr[arrIndex] > pivot) {
                swap(arr, arrIndex, sortIndex);
                sortIndex++;
            }
        }
        swap(arr, sortIndex, right);
        return sortIndex;
    }

    public static void swap(int[] arr, int i, int j) {
        if (i == j) return;
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }


}

修改了 quickSort 方法中第2行的代码，这里的思路是 quickSort 方法中的第2行和第9行都调用了 partition 方法，我希望可以把它们统一起来，于是我给p赋值为-1，统一调用while循环中的partition方法。

4.0：

这个版本是对3.0版本的调整优化：

public class KthNum {
    public static int k = 4;

    public static void main(String[] args) {
        int arr[] = {3, 2, 3, 1, 7, 4, 5, 5, 6};
        int kNum = quickSort(arr);
        System.out.println("kNum=" + kNum);
    }

    public static int quickSort(int arr[]) {
        int length = arr.length;
        if (k <= 0 || k > length) throw new RuntimeException("K值不合理");
        int left = 0, right = length - 1;
        int p = -1;
        while (k != p + 1) {
            if (k < p + 1) {
                right = p - 1;
            } else if (k > p + 1) {
                left = p + 1;
            }
            p = partition(arr, left, right);
        }
        return arr[p];
    }

    public static int partition(int[] arr, int left, int right) {
        int pivot = arr[right];
        int sortIndex = left;
        for (int arrIndex = sortIndex; arrIndex < right; arrIndex++) {
            if (arr[arrIndex] > pivot) {
                swap(arr, arrIndex, sortIndex);
                sortIndex++;
            }
        }
        swap(arr, sortIndex, right);
        return sortIndex;
    }

    public static void swap(int[] arr, int i, int j) {
        if (i == j) return;
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }


}

优化点：

1. 将 quickSort 方法的局部参数 left 和 right 放到方法内部赋值

2. 移除了原quickSort 方法中 left 和 right 的比较

3. quickSort 方法中添加了 K 值合理性的判断

4.0小结发散思考：

至此，快排计算第K大的数就完成了。我们还是发散思考一下，既然第K大的数，那么肯定也有求第K小的数的需求。带着这个问题，我们重新审视一下上述4.0的代码，可以得出2种方案：

1. 既然求第K大的数在while循环中可以通过K和P+1，在不同的区间范围排序查找。那么同理，求第K小的数也可以通过K和P的关系算出来。

2. 上述 partition 方法中是通过倒序的方式求第K大的数，那么求第K小的数只需要采用升序的方式即可。

4.1：

这个版本就是4.0小结中的求第K小的数的第1种解决方案：

public class KthNum {
    public static int k = 3;
    public static boolean bigK = false;

    public static void main(String[] args) {
        int arr[] = {3, 2, 3, 1, 7, 4, 5, 5, 6};
        int kNum = quickSort(arr);
        System.out.println("kNum=" + kNum);
    }

    public static int quickSort(int arr[]) {
        int length = arr.length;
        if (k <= 0 || k > length) throw new RuntimeException("K值不合理");
        int left = 0, right = length - 1;
        int p = bigK ? -1 : partition(arr, left, right);
        while (k != (bigK ? p + 1 : length - p)) {
            if (bigK ? k < p + 1 : k > length - p) {
                right = p - 1;
            } else if (bigK ? k > p + 1 : k < length - p) {
                left = p + 1;
            }
            p = partition(arr, left, right);
        }
        return arr[p];
    }

    public static int partition(int[] arr, int left, int right) {
        int pivot = arr[right];
        int sortIndex = left;
        for (int arrIndex = sortIndex; arrIndex < right; arrIndex++) {
            if (arr[arrIndex] > pivot) {
                swap(arr, arrIndex, sortIndex);
                sortIndex++;
            }
        }
        swap(arr, sortIndex, right);
        return sortIndex;
    }

    public static void swap(int[] arr, int i, int j) {
        if (i == j) return;
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }


}

代码的改动是涉及K和P的关系的比较，属于一个逆势思维。在一串倒序的数中求第K小的数，例如在7, 6, 5, 5, 4, 3, 3, 2, 1 这组数中6是第2大的数，是第8小的数。有兴趣的可以看下，不过重点推荐5.0版本的实现方案。

5.0：

这个版本就是4.0小结中的求第K小的数的第2种解决方案：

public class KthNum {
    public static int k = 2;
    public static boolean bigK = false;

    public static void main(String[] args) {
        int arr[] = {3, 2, 3, 1, 7, 4, 5, 5, 6};
        int kNum = quickSort(arr);
        System.out.println("kNum=" + kNum);
    }

    public static int quickSort(int arr[]) {
        int length = arr.length;
        if (k <= 0 || k > length) throw new RuntimeException("K值不合理");
        int left = 0, right = length - 1;
        int p = -1;
        while (k != p + 1) {
            if (k < p + 1) {
                right = p - 1;
            } else if (k > p + 1) {
                left = p + 1;
            }
            p = partition(arr, left, right);
        }
        return arr[p];
    }

    public static int partition(int[] arr, int left, int right) {
        int pivot = arr[right];
        int sortIndex = left;
        for (int arrIndex = sortIndex; arrIndex < right; arrIndex++) {
            if (bigK ? arr[arrIndex] > pivot : arr[arrIndex] < pivot) {
                swap(arr, arrIndex, sortIndex);
                sortIndex++;
            }
        }
        swap(arr, sortIndex, right);
        return sortIndex;
    }

    public static void swap(int[] arr, int i, int j) {
        if (i == j) return;
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }


}

这里新增了一个成员变量 bigK 来做标识：true代表求第K大的数；false代表求第K小的数。同时在 partition 方法中的第4行也做了改动：若bigK为true，则采用倒序；若bigK为false，则采用升序。这样就以最小的改动实现了求第K大的数和第K小的数的需求，完美。

收起

展开全文

快速排序

数组中求第K大数的实现方法
2021-01-20 06:41:08

问题：有一个大小为n的数组A[0,1,2,…,n-1]，求其中第k大的数。该问题是一个经典的问题，在《算法导论》中被作为单独的一节提出，而且其解决方法很好的利用了分治的思想，将时间复杂度控制在了O(n)，这多少出乎我们...

收起
求有N个元素的数组中前k个最大的数？(N>=k)（python实现）
2021-01-20 02:09:15

由于只需要找出前k大的数，因此没必要对数组中所有的元素排序，可以采用部分排序的方式。具体思路为：第一次先遍历数组找到最大的数，第二次遍历从剩下的数组中找到最大的数（在整个数组中第二大的数）…共需遍历k次...

收起

python 数组
【算法】在N个乱序数字中查找第K大的数字
万次阅读 2018-09-03 12:35:23
目录 1. 结论 2. 经典的几种解法 2.1 解法一：O(n*k) 2.2 解法二：O(n*logk) 2.3 解法三：O(n) 2.4 解法四：O(n*logn+k) ...在N个乱序数字中查找第k大的数字,时间复杂度可以减小至O(N)。 ...
目录

1. 结论

2. 经典的几种解法

2.1 解法一：O(n*k)

2.2 解法二：O(n*logk)

2.3 解法三：O(n)

2.4 解法四：O(n*logn+k)

2.5 解法五：O(n*logn)

2.6 解法六：O(4*n+k*logn)

2.7 解法七：O(n)

Reference

1. 结论

在N个乱序数字中查找第k大的数字,时间复杂度可以减小至O(N)。

2. 经典的几种解法

2.1 解法一：O(n*k)

思想：利用冒泡排序或者简单选择排序，K次选择后即可得到第k大的数。总的时间复杂度为O(n*k)。

2.2 解法二：O(n*logk)

思想：维护一个k大小的最小堆，对于数组中的每一个元素判断与堆顶的大小，若堆顶较大，则不管，否则，弹出堆顶，将当前值插入到堆中。时间复杂度O(n * logk)。

2.3 解法三：O(n)

思想：利用快速排序的思想，从数组S中随机找出一个元素X，把数组分为两部分Sa和Sb。Sa中的元素大于等于X，Sb中元素小于X。这时有两种情况：

1. Sa中元素的个数小于k，则Sb中的第k-|Sa|个元素即为第k大数；

2. Sa中元素的个数大于等于k，则返回Sa中的第k大数。

时间复杂度近似为O(n)。

代码实现：
```
public class disorderSearchBin {
	
	 public static int quickSortOneTime(int[] array, int low, int high){ //一趟快速排序   
		 int  key = array[low];  
         while(low < high){  
        	while(key < array[high] && low < high)  high--;
            array[low] = array[high];  
            while(key > array[low] && low < high)   low++;  
            array[high] = array[low];
         }  
	    array[high] = key;  
	    return high;
	    }  
	 
	 public static int Select_k(int[] array, int low, int high, int k) {
		 int index;
		 if(low == high) return array[low];
		 int partition = quickSortOneTime(array, low, high);
		 index = high - partition + 1;  //找到的是第几个大值
		 if(index == k) {
			 return array[partition];
		 }else if(index < k) {//此时向左查找
			 return Select_k(array, low, partition-1, k-index);  //查找的是相对位置的值，k在左段中的下标为k-index
		 }else {
			 return Select_k(array, partition+1, high, k);
		 }
	 }
 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		 int[] array = new int[] {92, 5, 88, 13, 80};   
	     int index = Select_k(array, 0, array.length-1, 2);
	     System.out.print(index);
	}
 
}
```
注：以上三种解法需要完全熟练掌握。

2.4 解法四：O(n*logn+k)

思想：对这个乱序数组用堆排序、快速排序、或者归并排序算法按照从大到小先行排序，然后取出前k大，总的时间复杂度为O(n*logn + k)。

2.5 解法五：O(n*logn)

思想：二分[Smin,Smax]查找结果X，统计X在数组中出现，且整个数组中比X大的数目为k-1的数即为第k大数。时间复杂度平均情况为O(n*logn)。

2.6 解法六：O(4*n+k*logn)

思想： 用O(4*n)的方法对原数组建最大堆，然后pop出k次即可。时间复杂度为O(4*n + k*logn)。

2.7 解法七：O(n)

思想：利用hash保存数组中元素Si出现的次数，利用计数排序的思想，线性从大到小扫描过程中，前面有k-1个数则为第k大数，平均情况下时间复杂度O(n)。

Reference

【1】https://blog.csdn.net/program_developer/article/details/80348077

【2】https://www.nowcoder.com/questionTerminal/62343a8ba8894379b8a3e5e30a745ace

【3】https://www.cnblogs.com/zhjp11/archive/2010/02/26/1674227.html
收起
展开全文
算法
【算法】寻找第k大的数
千次阅读 2018-12-02 12:18:28

本文中需要寻找第k大的数，笔者目前想到3个方法可解决它。 2、排序解决法如果是一个有序数组，那么寻找第k的大数则相当简单了，且效率为1。数组排序算法中相对较优的算法为快速排序，效率...

收起
在N个数中查找第K大的数字（Top K问题）
千次阅读 2019-09-07 22:32:54

在N个乱序数字中查找第k大的数字，时间复杂度可以减小至 O(N*logN) O(N) O(1) O(2) 答案：B 所谓“第（前）k大数问题”指的是在长度为n(n>=k)的乱序数组中S找出从大到小顺序的第（前）k个数的问题。注意...

收起
寻找第k大的数的方法总结
千次阅读 2017-11-18 13:55:54

名称是：设计一组N个数，确定其中第k个最大值，这是一个选择问题，当然，解决这个问题的方法很多，本人在网上搜索了一番，查找到以下的方式，决定很好，推荐给大家。所谓“第（前）k大数问题”指的是在长

收起
找出数组中第k大小的数，输出数所在的位置
2019-12-18 10:14:01

找出数组中第k大小的数，输出数所在的位置 /*写一段程序，找出数组中第k大小的数，输出数所在的位置。例如{2，4，3，4，7}中，第一大的数是7，位置在4。第二大、第三大的数都是4，位置在1、3随便输出哪一个均可。*/...

收起

c++
C++ 快排思想求第k大的数据（3种方法）、第k小的数据（3种方法）
千次阅读 2018-08-22 22:08:42

C++ 快排思想求第k大的数据（2种思路）、第k小的数据（1种...//找出数组中第k大的数法1 二路快排1 int quicksort_k_big1(int a[], int l, int r, int k)//从大到小排序 { if (l &gt;= r) return a[l]; ...

收起

快排的应用
求两个有序数组合并后第K大值-leetcode
千次阅读 2019-03-28 17:59:36

两个有序数组从小到大排列，取两个数组合并后第K大的元素，要求O(1)空间复杂度如 a = {0, 1, 2, 4} b = {3, 5, 7} 第4大元素，返回3 方法一：不考虑复杂度的情况下，首先想到的方法是一次从两个数组中选取较...

收起

算法
寻找数组中第k大的数
千次阅读 2020-08-30 11:30:45

给定一个整数数组a,同时给定它的大小n和要找的K(K在1到n之间)，请返回第K大的数，保证答案存在。测试样例： [1,3,5,2,2],5,3 返回： 2 方法一：利用冒泡排序，进行k趟排序，即可查找到第k大的数（每趟冒泡...

收起

java
【LeetCode】快排-无序整数数组中找第k大的数(或者最小的k个数)
千次阅读 2020-05-21 20:19:29

一个有代表性的题目：无序整数数组中找第k大的数，对快排进行优化。这里先不说这个题目怎么解答，先仔细回顾回顾快排，掰开了揉碎了理解理解这个排序算法：时间复杂度、空间复杂度；什么情况下是复杂度最高的情况...

收起

java 快速排序排序算法
求无序数组中第k大的数
千次阅读 2018-10-08 11:09:00

我们知道快速排序就是找一个哨兵，使左边的数比它大，右边的数比它小，然后在对左右两边的数重复上次的动作。可以利用快速排序中的步骤，找的哨兵，在排完一步的序后，如果等于$k，则这个位置就是要找的，如果小于...

收起
java寻找数组中第k大的数
千次阅读 2019-10-08 22:13:22

堆排序找第k大的数，先构建大根堆，求第k大的数，就调整k次，然后输出arr[len-k]位置的数 public static void swap ( int arr [ ] , int a , int b ) { int temp = arr [ a ] ; arr [ a ...

收起
Java找出数组中第K大的数
2020-10-26 15:55:43

给定一个整数数组a,同时给定它的大小n和要找的K(K在1到n之间)，请返回第K大的数，保证答案存在。测试样例： [1,3,5,2,2],5,3 返回：2 import java.util.*; public class Finder { public int findKth...

收起
求一个数组中前K大的数或者第K大的数
千次阅读 2017-09-16 14:53:12

求一个数组中前K大的数（或者第K大的数），该数组不能使用排序算法，时间复杂度小于O(n^2)。 #include using namespace std; void BubbleSort(int a[], int alen) { for(int i = 0; i ; i++) { for(int j ...

收起
Leetcode-215：求一个数组中第k大的数
千次阅读 2018-08-13 23:38:51

给定一个未排序的整数数组，找到其中第k大的数样例：给出数组[4,5,1,2,3]和k=3，返回3；给出数组[7,9,4,5]和k=1，返回9. 要求时间复杂度为O(n)，空间复杂度为O(1) 分析快排–不用完全快排完成：因为快...

收起

数据结构与算法 C语言快速排序
算法-寻找第K大的数的方法总结
千次阅读 2019-06-25 15:07:00

转载：... 解法3： void findKthBigger(vector<int> &a, int K, int m, int n) { int i = m, j = n; int base = a[i]; while (i<j) { ...

收起
python实现查找数组中第k大的数
千次阅读 2020-02-03 14:44:35

本文用python3实现查找数组中第k大的数。采用快速排序的方法实现。 def findKth(s, k): return findKth_c(s, 0, len(s) - 1, k) def findKth_c(s, low, high, k): m = partition(s, low, high) if m == len...

收起

python 快速排序
快速排序求第 K 大的数或第 K 小的数
千次阅读 2019-03-16 09:31:17

众所周知，快速排序可以通过每一趟排序将指定元素放在它...假如我们要找的是第 K 大的数，而一趟快排后 a[low] 这个元素被放在了指定位置，那就只需要看 K 和 low 的大小关系来决定递归 low 的左边部分还是右边部...

收起
寻找第（前）k大的数的方法总结
千次阅读 2016-09-08 23:00:32

给定一个包含n个数的乱序数组，寻找其中第k大的数。方法总结解法1：先将乱序数组按照从大到小排序，然后取出第k大的数。时间复杂度为O(n*logn)。解法2：利用选择排序，k次选择后即可得到第k大的数。时间...

收起
常见题：无序数组中第k大的数（python）
千次阅读 2020-04-09 16:48:00

先对数组排序，然后找出第k个位置 sorted(nums)[-k] 算法的时间复杂度为 O(N log N)，空间复杂度为 O(1) 思路二：利用快排思想 (https://blog.csdn.net/wenqiwenqi123/article/details/81669899) 快速排序每次把一...

收起

算法 python
N个数中找到第K大的数值（C语实现）
千次阅读 2020-09-22 11:26:40

研究生了，选了计算机算法这门课程，这周布置了一个作业，在OJ上做：**N个数中找到第K大的数值**。大一简单学过C语言基础，目前只能用C语言编程，后续会学C++编程。分享一份不超时的C语代码~ 测试例子：思路： ...

收起

c算法算法
【leetcode】找出数组的第k大的数
千次阅读 2019-08-10 18:39:42

找出数组的第k大的数：[6,7,8,9, 3, 2, 4, 8]第3大的数是4 ''' class Solution: def call(self, nums, k): if nums == None or len(nums) == 0: return -1 result = self.qsort(nums, 0, len(nums) - 1, k) ...

收起
C语言——用堆实现求N个数中第K大的数
千次阅读 2018-11-28 00:28:54

问题描述：在N（0<N<100000）个数中，找出第K（0<k<100000）大的数。例如：1,2,3,4,5,6,7,8,9 中第3大的数为 7。...第一行包括两个数，一个正整数N和...对于每组数据，输出一个数，表示第K大的数，并...

收起
寻找第K大的数（快排思想）
万次阅读 2016-04-15 22:27:19

使用快排思想找第K大的数，算法复杂度O（n）。1.以数组a的第0位a[0]为参考基准base，将数组划分为两个部分；如果找第K大的数，则将大于base的数往前挪，将小于base的数往后挪。如果找第K小的数，则与此相反。 ...

收起

快速排序与查找第K大的数

快速排序

快速排序C++实现

查找第K大的数

快排思想实现查找第K大的数

C++实现

查找数组中第k大的数

C++——寻找第k大的数

求N个数中第K大的数

快速排序计算第K大的数

1.0：

1.0小结：

1.1：

2.0：

3.0：

4.0：

4.0小结发散思考：

4.1：

5.0：

数组中求第K大数的实现方法

求有N个元素的数组中前k个最大的数？(N>=k)（python实现）

【算法】在N个乱序数字中查找第K大的数字

1. 结论

2. 经典的几种解法

2.1 解法一：O(n*k)

2.2 解法二：O(n*logk)

2.3 解法三：O(n)

2.4 解法四：O(n*logn+k)

2.5 解法五：O(n*logn)

2.6 解法六：O(4*n+k*logn)

2.7 解法七：O(n)

Reference

【算法】寻找第k大的数

在N个数中查找第K大的数字（Top K问题）

寻找第k大的数的方法总结

找出数组中第k大小的数，输出数所在的位置

C++ 快排思想 求第k大的数据（3种方法）、第k小的数据（3种方法）

求两个有序数组合并后第K大值-leetcode

寻找数组中第k大的数

【LeetCode】快排-无序整数数组中找第k大的数(或者最小的k个数)

求无序数组中第k大的数

java寻找数组中第k大的数

Java找出数组中第K大的数

求一个数组中前K大的数或者第K大的数

Leetcode-215：求一个数组中第k大的数

算法-寻找第K大的数的方法总结

python实现查找数组中第k大的数

快速排序求第 K 大的数或第 K 小的数

寻找第（前）k大的数的方法总结

常见题：无序数组中第k大的数（python）

N个数中找到第K大的数值（C语实现）

【leetcode】找出数组的第k大的数

C语言——用 堆 实现求N个数中第K大的数

寻找第K大的数（快排思想）

2.6 解法六：O(4n+klogn)

C++ 快排思想求第k大的数据（3种方法）、第k小的数据（3种方法）

C语言——用堆实现求N个数中第K大的数