首页 > 代码库 > LeetCode75 Sort Colors
LeetCode75 Sort Colors
题目:
Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
Note:
You are not suppose to use the library‘s sort function for this problem. (Medium)
分析:
最直观的想法就是遍历一遍数个数,再遍历一遍按照0,1,2的个数赋值。但题目的follow-up中也提出了不要这么做。
一次遍历常数空间的算法就是采用双指针,模拟快排的思路移动元素。
p1左侧表示0(如果有),p2右侧表示2(如果有)。
这样一次遍历:
遇到0,则swap(nums[i], nums[p1]) p1++
遇到2,则swap(nums[i], nums[p2])p2--, 并且再判定一次i位置
遇到1则 不操作。
代码:
1 class Solution { 2 public: 3 void sortColors(vector<int>& nums) { 4 int p1 = 0, p2 = nums.size() - 1; 5 for (int i = 0; i <= p2; ++i) { 6 if (nums[i] == 0) { 7 swap(nums[i], nums[p1]); 8 p1++; 9 }10 else if (nums[i] == 2) {11 swap(nums[i], nums[p2]);12 p2--;13 i--;14 }15 }16 return;17 }18 };
LeetCode75 Sort Colors
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。