leetcode每日一题(2020.10.07) 75. 颜色分类(中等)

文章目录

计数法单指针：两次遍历双指针(官方写法)：一次遍历双指针另一写法双指针简洁版 75. 颜色分类(中等)

计数法

class Solution { public void sortColors(int[] nums) { int c1 = 0; int c2 = 0; int c3 = 0; //计数 for(int num: nums){ if(num == 0){ c1++; }else if(num == 1){ c2++; }else{ c3++; } } //重写数组 for(int i = 0; i < nums.length; i++){ if(i < c1){ nums[i] = 0; }else if(i < c1+c2){ nums[i] = 1; }else{ nums[i] = 2; } } } }

单指针：两次遍历

//两次遍历，常数空间复杂度 /* 在第一次遍历中，我们从左向右遍历整个数组，如果找到了 0，那么就需要将 0 与「头部」位置的元素进行交换，并将「头部」向后扩充一个位置。在遍历结束之后，所有的 0 都被交换到「头部」的范围，并且「头部」只包含 0。 在第二次遍历中，我们从「尾部」开始，从右向左遍历整个数组，如果找到了 2，那么就需要将 2 与「尾部」位置的元素进行交换，并将「尾部」向前扩充一个位置。在遍历结束之后，所有的 2 都被交换到「尾部」，此时 2 只出现在「尾部」的位置，因此排序完成。 */ class Solution { public void sortColors(int[] nums) { int ptr = 0; for(int i = 0; i < nums.length; i++){ if(nums[i] == 0){ int tmp = nums[i]; nums[i] = nums[ptr]; nums[ptr] = tmp; ptr++; } } ptr = nums.length-1; for(int i = nums.length-1; i >= 0; i--){ if(nums[i] == 2){ int tmp = nums[i]; nums[i] = nums[ptr]; nums[ptr] = tmp; ptr--; } } } }

双指针(官方写法)：一次遍历

/* 此处需要注意，一次遍历，遍历到0的时候，前面的0和2已经处理过了，所以直接交换，然后++即可；但是遍历到2的时候，由于要和后面的交换，而后面的元素还没有被处理过，所以交换后可能会出现0或2的情况，所以2要用while一直循环，还要放到上面，因为判别完2以后，还要判别是不是0 */ class Solution { public void sortColors(int[] nums) { int n = nums.length; int p0 = 0, p2 = n - 1; for (int i = 0; i <= p2; ++i) { while (i <= p2 && nums[i] == 2) { int temp = nums[i]; nums[i] = nums[p2]; nums[p2] = temp; --p2; } if (nums[i] == 0) { int temp = nums[i]; nums[i] = nums[p0]; nums[p0] = temp; ++p0; } } } } // 作者：LeetCode-Solution // 链接：https://leetcode-cn.com/problems/sort-colors/solution/yan-se-fen-lei-by-leetcode-solution/ // 来源：力扣（LeetCode） // 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

双指针另一写法

class Solution { public void sortColors(int[] nums) { int n = nums.length; //双指针 int p = 0, q = n - 1; for (int i = 0; i <= q; ++i){ //此处为什么要=q，因为q后面的元素才是2，q处的元素还未被处理 if (nums[i] == 0){ nums[i] = nums[p]; nums[p] = 0; ++p; }else if (nums[i] == 2){ nums[i] = nums[q]; nums[q] = 2; --q; --i; } } } };

双指针简洁版

class Solution { public void sortColors(int[] nums) { int left = 0, right = nums.length - 1; for(int i = 0; i <= right; i++){ if(nums[i] == 0){ nums[i] = nums[left]; nums[left++] = 0; }else if(nums[i] == 2){ nums[i--] = nums[right]; nums[right--] = 2; } } } }