quick selection：从move zeroes到荷兰国旗再到find first missing positive

最近复习发现许多题目背后有共性，需要基本功扎实。回顾快排发现，   每一个小步骤在leetcode的前500题已经有涉及了。


这里做个简要整理， 串起来，希望对大家有帮助。新人报到，求大米支持！ 谢谢大家
题目列表：

• move zeroes：https://leetcode.com/problems/move-zeroes
• sort color：https://leetcode.com/problems/sort-colors/
• find kth largest：https://leetcode.cn/problems/kth-largest-element-in-an-array/
• first missing positive： https://leetcode.cn/problems/first-missing-positive/description/

快排的关键在于划分。需要根据pivot值将待排序子数组进行划分。划分成两部分是常规做法，   可以通过move zeroes 练习，这虽然是简答题，但直接得出最优解（一遍、就地完成）需要深入理解partition。


两路划分有哪些问题？（1）如果数据已经有序，递归划分每一步只会减少一个元素，时间复杂度是1+2+...+n=n(n+1)/2 = n*n ,是最差的时间复杂度。随机选择pivot可以皮避免这个问题：例如当前我们是取最后一个元素为pivot，那么可以随机选择一个下标，将当前下标和末尾下标的值交换。这样保证了随机性，又保证了形式上的简单。

  x = rand(right - left) + left  #随机选择一个下标

  nums[x], nums[right] = nums[right], nums[x] # 交换

（2）如果数据中有大量重复元素， 那么一次划分后，后续会在当前划分的基础上多次重复划分。  解决办法是三路划分。 选定pivot后，将数组划分成大于、小于、等于pi vot值的三组，并返回等于pivot值的子数组的起末下标位置。   再后续排序划分时，只在pivot起末区间以外进行递归划分。 例如当前数组为{2,0,0,0,0,-1,0}, 划分后为{-1, 0,0,0,0,0,2},（其中pivot为0）返回的pivot起末区间为[1,5],那么后续递归时，只在[0, 1]和[6,6]两个子区间上进行。避免了两路划分时的大量重复计算。  
三路划分的抽象题目是荷兰国旗问题： sort colors ，实际应用时，将0、2分别视为小于、等于pivot的元素处理，并设置返回值为1（等于pivot）的起、末下标数组。 这个题目看上去不难，但是要一次bug free ，需要对loop invarient有正确认识。




再看具体应用：
（1） find kth largest element ： 这个可以通过设置capacity=k的最小堆来解，但复杂度是高于线性的。使用quick selection，可以得到amortized 复杂度为o(n)的解法。但是：如果不设置随机取pivot，会超时。近期新优化，如果不做三路划分，也会超时。 示例解法可见： 这里 。


（2）first missing positive ： 这题的官解不佳，需要遍历数组三趟，操作过多，优点绕。  如果理解了荷兰国旗问题（三路划分+循环不变量），可以较快解出，一遍完成。 参考：这里 。 思路的关键在于： 假定左边、右边的区间都是符合要求的，对中间待定区间进行判断，除了需要交换进行下一步判断的场景外，每一步都能缩小一步。这样最多遍历次数不多于两趟。

逆序对也可以用类似的思路，挺tricky的，比裸题稍微多一点思维难度。

感谢楼主分享！已加米