精华内容
下载资源
问答
  • 快速排序与查找第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(n
    k)
    解法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(4
    n)的方法对原数组建最大堆,然后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);
        }
    };

     

    展开全文
  • 求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,使用下标+1K进行比较,若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小的数的需求,完美。

     

    展开全文
  • 问题:有一个大小为n的数组A[0,1,2,…,n-1],求其中第k大。该问题是一个经典的问题,在《算法导论》中被作为单独的一节提出,而且其解决方法很好的利用了分治的思想,将时间复杂度控制在了O(n),这多少出乎我们...
  • 由于只需要找出前k大,因此没必要对数组中所有的元素排序,可以采用部分排序的方式。具体思路为:一次先遍历数组找到最大的二次遍历从剩下的数组中找到最大的(在整个数组中二大的)…共需遍历k次...
  • 目录 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大的数字,时间复杂度可以减小至 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大小,输出所在的位置 /*写一段程序,找出数组中第k大小,输出所在的位置。例如{2,4,3,4,7}中,第一是7,位置在4。 第二、第三都是4,位置在1、3随便输出哪一个均可。*/...
  • C++ 快排思想 求第k大的数据(2种思路)、第k小的数据(1种...//找出数组中第k大 法1 二路快排1 int quicksort_k_big1(int a[], int l, int r, int k)//从大到小排序 { if (l &amp;gt;= r) return a[l]; ...
  • 两个有序数组从小到大排列,取两个数组合并后第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大(每趟冒泡...
  • 一个有代表性的题目:无序整数组中找第k大,对快排进行优化。 这里先不说这个题目怎么解答,先仔细回顾回顾快排,掰开了揉碎了理解理解这个排序算法:时间复杂度、空间复杂度;什么情况下是复杂度最高的情况...
  • 求无序数组中第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 ...
  • 给定一个整数组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大),该数组不能使用排序算法,时间复杂度小于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) 分析 快排–不用完全快排完成: 因为快...
  • 算法-寻找第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...
  • 众所周知,快速排序可以通过每一趟排序将指定元素放在它...假如我们要找的是 K ,而一趟快排后 a[low] 这个元素被放在了指定位置,那就只需要看 K 和 low 的大小关系来决定递归 low 的左边部分还是右边部...
  • 寻找(前)k大的方法总结

    千次阅读 2016-09-08 23:00:32
    给定一个包含n个的乱序数组,寻找其中第k大。 方法总结 解法1:先将乱序数组按照从大到小排序,然后取出第k大。时间复杂度为O(n*logn)。 解法2:利用选择排序,k次选择后即可得到第k大。时间...
  • 先对数组排序,然后找出第k个位置 sorted(nums)[-k] 算法的时间复杂度为 O(N log N),空间复杂度为 O(1) 思路二:利用快排思想 (https://blog.csdn.net/wenqiwenqi123/article/details/81669899) 快速排序每次把一...
  • 研究生了,选了计算机算法这门课程,这周布置了一个作业,在OJ上做:**N个中找到第K大的数值**。大一简单学过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) ...
  • 问题描述: 在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小的,则与此相反。 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,065,383
精华内容 426,153
关键字:

第k大的数

友情链接: 1830534.rar