75. Sort Colors 发表于 2022-09-28 Swap1234567891011121314151617181920212223class Solution { public void sortColors(int[] nums) { int orderedIndex = -1; for (int i = orderedIndex + 1; i < nums.length; i++) { if (nums[i] == 0) { swap(nums, i, ++orderedIndex); } } for (int i = orderedIndex + 1; i < nums.length; i++) { if (nums[i] == 1) { swap(nums, i, ++orderedIndex); } } } private void swap(int[] nums, int i, int j) { int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; }} Swap123456789101112131415161718class Solution { public void sortColors(int[] nums) { int zeroEndIndex = 0, oneEndIndex = 0, twoEndIndex = 0; for (int i = 0; i < nums.length; i++) { if (nums[i] == 2) { nums[twoEndIndex++] = 2; } else if (nums[i] == 1) { nums[twoEndIndex++] = 2; nums[oneEndIndex++] = 1; } else { nums[twoEndIndex++] = 2; nums[oneEndIndex++] = 1; nums[zeroEndIndex++] = 0; } } }} Swap123456789101112131415161718192021222324252627class Solution { public void sortColors(int[] nums) { // ordered: // 0: [0, left - 1] // 2: [right + 1, nums.length - 1] int left = 0, right = nums.length - 1; // 下一个填入 0 的索引,下一个填入 2 的索引 int i = 0; while (i <= right) { if (nums[i] == 0) { swap(nums, i++, left++); } else if (nums[i] == 2) { // 交换至 nums[i] 的值可能为 0, 1, 2, 所以不推进 i 索引,而是要根据具体的值重新进入 while 循环继续处理 swap(nums, i, right--); } else { // nums[i] == 1 i++; } } } private void swap(int[] nums, int i, int j) { int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; }} Reference75. Sort Colors