题目概览给定一个包含红色、白色和蓝色、共n个元素的数组nums原地对它们进行排序使得相同颜色的元素相邻并按照红色、白色、蓝色顺序排列。我们使用整数0、1和2分别表示红色、白色和蓝色。必须在不使用库内置的 sort 函数的情况下解决这个问题。示例 1输入nums [2,0,2,1,1,0]输出[0,0,1,1,2,2]示例 2输入nums [2,0,1]输出[0,1,2]提示n nums.length1 n 300nums[i]为0、1或2进阶你能想出一个仅使用常数空间的一趟扫描算法吗来源75. 颜色分类 - 力扣LeetCode解题分析方法双指针定义两个指针 a 和 ba 负责 0 的交换b 负责 1 的交换则b 指针的位置一定小于等于 a令 a、b 初始值都为 0当当前元素为 0 时与 a 进行交换a若此时 b 小于 ab若交换后的元素为 1与 b 进行交换b当当前元素为 1 时与 b 进行交换b时间复杂度O(n)空间复杂度O(1)class Solution { public void sortColors(int[] nums) { int a 0, b 0; for (int i 0; i nums.length; i) { if (nums[i] 0) { swap(nums, a, i); a; if (b a) { b; } } if (nums[i] 1) { swap(nums, b, i); b; } } } private void swap(int[] nums, int i, int j) { int temp nums[i]; nums[i] nums[j]; nums[j] temp; } } JAVA练习325- 颜色分类
题目概览给定一个包含红色、白色和蓝色、共n个元素的数组nums原地对它们进行排序使得相同颜色的元素相邻并按照红色、白色、蓝色顺序排列。我们使用整数0、1和2分别表示红色、白色和蓝色。必须在不使用库内置的 sort 函数的情况下解决这个问题。示例 1输入nums [2,0,2,1,1,0]输出[0,0,1,1,2,2]示例 2输入nums [2,0,1]输出[0,1,2]提示n nums.length1 n 300nums[i]为0、1或2进阶你能想出一个仅使用常数空间的一趟扫描算法吗来源75. 颜色分类 - 力扣LeetCode解题分析方法双指针定义两个指针 a 和 ba 负责 0 的交换b 负责 1 的交换则b 指针的位置一定小于等于 a令 a、b 初始值都为 0当当前元素为 0 时与 a 进行交换a若此时 b 小于 ab若交换后的元素为 1与 b 进行交换b当当前元素为 1 时与 b 进行交换b时间复杂度O(n)空间复杂度O(1)class Solution { public void sortColors(int[] nums) { int a 0, b 0; for (int i 0; i nums.length; i) { if (nums[i] 0) { swap(nums, a, i); a; if (b a) { b; } } if (nums[i] 1) { swap(nums, b, i); b; } } } private void swap(int[] nums, int i, int j) { int temp nums[i]; nums[i] nums[j]; nums[j] temp; } } RELATED READING
延伸阅读
更多一线实战笔记与深度复盘，助您持续精进
