TopK问题 - 快速选择

快速选择的思路, 本质上是一种减分治的思路;

1 快速排序方式

排序方式本质上是通过对一组无序的数据进行有序化, 在将数组有序化后, 其中len-k的位置即为TopK;

而快速排序本质上就是通过分治的思路, 将问题化为子问题, 最终达到有序状态;

以简单的双指针单次快排思路为例;

2 引申 - 减分治思路

减分治思路即为, 我们在分治快排的过程中, 实际上会出现一种状态, 这种状态就是, 某个数实际上是已经在了他对应的位置当中, 其对应的条件即为(以Key为例):

Key的左侧<=Key && Key的右侧>=key

此时无论Key的左侧或是右侧是否有序, Key必然处于正确的位置;

那么只要符合这种条件, 我们就可以直接将TopK进行返回, 无需再进行递归分治;

3 二次减分治

所谓的二次减分治就是, 无论如何, 上述的方式都是基于同一种的分治思路, 但实际上在真正的TopK中, 我们并不需要要求Key的左右两侧都进行排序, 否则就是一种全排序;

• 那么如何进行二次减分治?

我们只需要在意, K的位置, 即n-k位置, 那么换句话来说就是, "K"在Key的左侧还是右侧;

若是此处的排序处理完后, K在Key的左侧, 那么我们只需要调整边界, 将下次索引的位置变为Key的左侧区间, 否则调整至Key的右侧区间;

将区间逐渐缩小, 当左右区间无法再进行细分时, 说明我们已经完整的命中了此处的目标;

那么只需要使用原生的Haore的方式, 对分治进行左右区分, 并且调整区间即可;

4 最终代码

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int n = nums.size();
        return quickSelect(nums, 0, n - 1, n - k);
    }
    int quickSelect(vector<int>& nums, int begin, int end, int K) {
        if(begin==end) return nums[K]; 
        int dividing = nums[begin];
        int left = begin-1;
        int right = end+1;
        while(left<right){
            do ++left; while(nums[left]<dividing); // 找比dividing大
            do --right; while(nums[right]>dividing); // 找比dividing小
            if(left<right) swap(nums[left], nums[right]);
        }
        if(K<=right) return  quickSelect(nums, begin, right, K);
        else return quickSelect(nums, right+1, end, K);
    }
};

在这段代码中, 本质的思路, 是通过单次的Hoare, 划分出一条中间线, 并判断TopK在左侧还是右侧, 从而逐渐缩小区间;

• 坑1

  在代码中, 有一段互补但看上去又像是脱裤子放屁的代码:

  int left = begin-1;
  int right = end+1;
  while(left<right){
  	do ++left; /*.......*/ while(nums[left]<dividing); // 找比dividing大
      do --right; /*.......*/ while(nums[right]>dividing); // 找比dividing小
  	/*.......*/
  }
  

  在这段代码中, 我们首先对left与right进行了蜜汁操作, 分别让他们往各自的方向走一步, 但在while循环体系中, 我们又采用do{ }while()的语法将其先进行++操作再判断while条件;

  这里看起来是一个无用的操作, 因为我们完全可以舍弃这个 begin-1, end+1与do{ }while(), 而是直接采用while的操作进行;

  但是这里实际上在价值体系中, 是begin-1, end+1需要为do{ }while()操作进行安全的界限隔离, 那么最主要的价值则是在do{ }while()中;

  假设有一组数据, 数据是 2, 2, 2, 2, 2, 2, 我们若是只用while, 那么在走循环的条件中, while(nums[left]<dividing)或是 while(nums[right]>dividing)时, 在进入while(left<right)循环体系后条件都会为假, 这迫使left指针与right指针不会移动, 从而造成死循环;

  do{ }while()则是强迫两个指针, 无论如何都需要往后走, 从而破除这种死循环的重要途径;

• 坑2

  在代码中, 和分隔线相关的代码内容, 我们所采用的是right部分而不是left部分, 本质上是因为, 在原生的Hoare算法中, right才是一个安全可以做分隔线的保障, 与快排中的双指针方法不同, 我们在代码中所采用的思路是do while, 先进行移动, 再进行判断;

  那么在这个while循环中, 两个指针必然不会因为left == right而停下, 且必然会错开;

  此时假设错开的条件为, right=0, left=1, 那么由于begin为0,且我们需要往左区间进行索引, 那么接下来传入的依旧是 func(0,1), 可能会造成死递归;

  因此我们必须将right线作为分隔线的安全保证, 无论是条件, 还是分隔线参数的传入;

• 坑3

  在代码中, 交换的逻辑与双指针思路并不相同, 这里的思路是需要通过判断再进行交换, 而不是无脑交换;

  就如问题2中描述的, 两个指针必然会错过;

  若是未将指针的交换强制为, left<right时进行交换, 必然会造成正确交换后的多一次交换;