题目描述:
给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。 此题中,我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。 注意: 不能使用代码库中的排序函数来解决这道题。 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/sort-colors 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
示例:
输入: [2,0,2,1,1,0] 输出: [0,0,1,1,2,2]
进阶:
· 一个直观的解决方案是使用计数排序的两趟扫描算法。 首先,迭代计算出0、1 和 2 元素的个数,然后按照0、1、2的排序,重写当前数组。 · 你能想出一个仅使用常数空间的一趟扫描算法吗?
题目难度:中等
分析:
简化题目,忽略颜色的干扰,可以理解为一个数组中只有0, 1, 2三个元素,然后对数组排序。我们知道数组排序算法最快的也是O ( n l o g n ) O(nlogn)O(nlogn),所以并不符合题意,当然只有3个元素也没有必要排序就是了,并且题目中也给了一个方法,此方法比较简单,不是本文的重点,不过依然会给出参考代码。
进阶:从最终结果来看,数组顺序必然是按照000111222来排列的,所以可以理解为:0元素都在最左边,1在中间,2在最右边,相同元素之间并没有顺序,所以首先应该有3个指针left, current, right,前两者在左,后者在右。然后遍历数组,遇0则left, current交换,然后两个指针同时右移,遇2则current, right交换,然后right指针左移,遇1则不交换,但是current右移即可。代码如下:
java:
class Solution { public void sortColors(int[] nums) { // 表示0, 1, 2三个元素的个数 int zeroCount = 0, oneCount = 0, twoCount = 0; for (int num : nums) { // 判断数字,同时对应的个数加1 switch (num) { case 0: zeroCount++; break; case 1: oneCount++; break; default: twoCount++; } } // 最后分别按照3个元素的个数修改数组中的元素即可 for (int i = 0; i < nums.length; i++) { if (zeroCount > 0) { nums[i] = 0; zeroCount--; } else if (oneCount > 0) { nums[i] = 1; oneCount--; } else { nums[i] = 2; } } } }
python:
class Solution: def sortColors(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ zero_count, one_count, two_count = 0, 0, 0 for num in nums: if num == 0: zero_count += 1 elif num == 1: one_count += 1 else: two_count += 1 for i in range(len(nums)): if zero_count > 0: nums[i] = 0 zero_count -= 1 elif one_count > 0: nums[i] = 1 one_count -= 1 else: nums[i] = 2
进阶版java:
class Solution { public void sortColors(int[] nums) { // 分别定义3个指针 int left = 0, current = 0, right = nums.length - 1; while (current <= right) { int num = nums[current]; // 如果num = 0则交换left, current if (num == 0) { swap(nums, left, current); left++; current++; // 如果num = 2则交换current, right } else if (num == 2) { swap(nums, current, right); right--; // 否则为1 } else { current++; } } } public void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } }
进阶版python:
class Solution: def sortColors(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ left, current, right = 0, 0, len(nums) - 1 while current <= right: num = nums[current] if num == 0: // python语法支持这样的交换值逻辑,所以并不需要定义交换值方法 nums[left], nums[current] = nums[current], nums[left] left += 1 current += 1 elif num == 2: nums[current], nums[right] = nums[right], nums[current] right -= 1 else: current += 1
总结:
普通版时间复杂度为O(2n),进阶版时间复杂度为O(n),此题如果不考虑进阶版应该是简单难度,进阶版如果知道了方法也很好理解,就是可能不太好想到此方法,多刷题即可。