[LeetCode]Sort Colors

这道题可以用3-way quick sort来解。当有很多重复的key的时候，Quick Sort的时间复杂度会退化到O(n^2)。3-way quick sort可以解决这个问题。我们用V来表示当前用来分割的数，lo，hi代表当前区间的上下界，lt，gt代表等于最终重复的V区间的上下界，i代表当前处理的数，如下图所示：

那么在我们i从左向右扫的过程中，有一点是不变的，那就是lt分割了<V和==V的区间，gt分割里>V和==V的区间，如下图所示：

那么我们的策略是：

• 如果当前数<V，swap lt和i的元素，并且lt++, i++
• 如果当前数>V，swap gt和i的元素，gt--，不变i因为gt换过来的元素我们还没有check过
• 如果当前数==V，i++

这样我们能保证我们的invariant是一直不会变的，当i大于gt的时候，算法结束，因为所有元素我们都扫过了，时间复杂度O(n)，代码如下：

	class Solution {
	public:
	void sortColors(vector<int>& nums) {
	int len = nums.size(), num = 1, lt = 0, gt = len - 1, i = 0;
	while(i <= gt)
	{
	if(nums[i] < num)
	swap(nums[lt++], nums[i++]);
	else if(nums[i] > num)
	swap(nums[gt--], nums[i]);
	else
	++i;
	}
	}
	};

view raw Sort Colors.cpp hosted with ❤ by GitHub