75. 颜色分类

 

我们对数组进行两次遍历将0和1全部调到前面，这样做时间复杂度相对低。

class Solution { public: void sortColors(vector<int>& nums) { int ptr = 0; for (int i = 0; i < nums.size(); ++i) { if (nums[i] == 0) { swap(nums[i], nums[ptr]); ++ptr; } } for (int i = ptr; i < nums.size(); ++i) { if (nums[i] == 1) { swap(nums[i], nums[ptr]); ++ptr; } } } };

接下来用双指针进行一次遍历

class Solution { public: void sortColors(vector<int>& nums) { int p0 = 0, p1 = 0; for (int i = 0; i < nums.size(); ++i) { if (nums[i] == 1) { swap(nums[i], nums[p1]); ++p1; } else if (nums[i] == 0) { swap(nums[i], nums[p0]); if (p0 < p1) //如果不进行判断会导致可能将最后一个0与1交换 { swap(nums[i], nums[p1]); } ++p0; ++p1; } } } };