给定一个包含红色、白色和蓝色、共 n
个元素的数组 nums
,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。
我们使用整数 0
、 1
和 2
分别表示红色、白色和蓝色。
必须在不使用库的sort函数的情况下解决这个问题。
示例 1:
输入:nums = [2,0,2,1,1,0] 输出:[0,0,1,1,2,2]
示例 2:
输入:nums = [2,0,1] 输出:[0,1,2]
提示:
n == nums.length
1 <= n <= 300
nums[i]
为0
、1
或2
进阶:
- 你可以不使用代码库中的排序函数来解决这道题吗?
- 你能想出一个仅使用常数空间的一趟扫描算法吗?
方法:双指针
1 /** 2 * @param {number[]} nums 3 * @return {void} Do not return anything, modify nums in-place instead. 4 */ 5 var sortColors = function (nums) { 6 let len = nums.length, cur = 0, p0 = 0, p1 = len - 1; 7 while (cur <= p1) { 8 function swap(a, b) { 9 let temp = nums[a]; 10 nums[a] = nums[b]; 11 nums[b] = temp; 12 } 13 if (nums[cur] === 0) { 14 swap(cur, p0); 15 cur++; 16 p0++; 17 } else if (nums[cur] === 2) { 18 swap(cur, p1); 19 p1--; 20 } else { 21 cur++; 22 } 23 } 24 };
标签:颜色,cur,nums,示例,分类,len,75,return From: https://www.cnblogs.com/icyyyy/p/16886382.html