力扣刷题-分治算法-215 第k个最大元素

题目描述

在未排序的数组中找到第 k 个最大的元素。请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。
示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
说明:
你可以假设 k 总是有效的,且 1 ≤ k ≤ 数组的长度。

这道题 想要考我们什么咧?
其实这道题是想考一个快速排序。

快速排序的原理就是 每一次能确定一个数的位置。

然后再对该数左右两边的数组用同样的方法 分治排好。

所以其实这道题的思路也很简单,首先就得对数组进行一次快速排序,然后确定一个数的位置,然后再根据我们要求的是第几个不同的元素,判断去排左边或者右边。

比如有6个元素,要求的是第五个,那么假设第一次排好的位置是3,就只需要找右边的,不要找左边的。

不过先熟悉一下快速排序吧,这个看我之前写过的快速排序算法。

快速排序算法

不过那里讲得有点基础,是从最原始开始推起,假设已经有点印象了,非常熟练了,其实是可以十分钟就写出来了,只要记住几个原则手写快速排序。

  1. 快速排序的整体思路就是每一次找出一个数的位置
  2. 然后再对该数位置左右两边运用同样的分治方法排好序。
  3. 那么如何找出一个数的位置呢?就是用两个指针,两个while循环,循环遍历就可以了,其实记住之后挺简单的。

 void quick_sort(int num[],int begin,int end) {
        int left = begin;
        int right = end;
        
        if (end < begin) return;//递归出口这里要注意!是end<begin!!! 就这里需要注意一下!

            int key = num[left];
            while (left < right) {
                while (left < right && num[right] > key) {
                    right--;
                }
                num[left] =num[right];//这边记得是数组两边交换
                left++;

                while (left < right && num[left] < key) {
                    left++;
                }
                num[right] = num[left];//这边记得是数组两边交换
                right--;
            }
            num[left] = key; //最后遍历循环一遍后,就把left==right的地方插上原本的数,就得到该数的位置了。
            //   System.out.println(num[left]);

            quick_sort(num, begin, left - 1);
            quick_sort(num, right + 1, end);
    }

好了,然后讲一下关于这道题的快速排序改装法,其实就是改装一下就可以了。

比如说要找第2个最大的元素,那么如果数组有6个数的话,其实也就是要找升序排序第4个数,也就是下标为3的数,所以要找第k个最大的数,我们可先算出n=nums.length-1-k算出下标

然后最主要就是在最后递归那里,因为我们已经得到一个数的位置了,现在判断,

  • 若该位置,就是所求的n,即返回该数
  • 若所求的在该位置右边,则进行右循环即可
  • 若所求的在该位置左边,则进行左循环即可

//最上面
        int l=num.length-k;
        注意这里的l 只需要减k,不用再减1,因为第一个位置最大,是从1开始,搞不懂建议写几个数推一下。



 if(l==leftkey)return num[leftkey];
        else if(l<leftkey)return sort22(num,begin,leftkey-1,k);
       else   if(l>leftkey)return sort22(num,rightkey+1,end,k);

          return -1;
上一篇:常用的魔术方法


下一篇:php如何删除数组指定键名的元素