给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。
我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库的sort函数的情况下解决这个问题。
思路与算法
class Solution { public void sortColors(int[] nums) { int n = nums.length; int ptr = 0; for (int i = 0; i < n; ++i) { if (nums[i] == 0) { int temp = nums[i]; nums[i] = nums[ptr]; nums[ptr] = temp; ++ptr; } } for (int i = ptr; i < n; ++i) { if (nums[i] == 1) { int temp = nums[i]; nums[i] = nums[ptr]; nums[ptr] = temp; ++ptr; } } } }
复杂度分析
- 时间复杂度:O(n),其中 n 是数组 nums 的长度。
- 空间复杂度:O(1)。
思路与算法
class Solution { public void sortColors(int[] nums) { int n = nums.length; int p0 = 0, p1 = 0; for (int i = 0; i < n; ++i) { if (nums[i] == 1) { int temp = nums[i]; nums[i] = nums[p1]; nums[p1] = temp; ++p1; } else if (nums[i] == 0) { int temp = nums[i]; nums[i] = nums[p0]; nums[p0] = temp; if (p0 < p1) { temp = nums[i]; nums[i] = nums[p1]; nums[p1] = temp; } ++p0; ++p1; } } } }
复杂度分析
- 时间复杂度:O(n),其中 n 是数组 nums 的长度。
- 空间复杂度:O(1)。
思路与算法
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; } } } }
复杂度分析
- 时间复杂度:O(n),其中 n 是数组 nums 的长度。
- 空间复杂度:O(1)。
class Solution { public void sortColors(int[] nums) { Listlist0 = new ArrayList<>(); List list1 = new ArrayList<>(); List list2 = new ArrayList<>(); for (int num : nums) { if(num==0)list0.add(num); if(num==1)list1.add(num); if(num==2)list2.add(num); } for (int i = 0; i < nums.length; i++) { if (i