看懂题目后直觉是 —— new一个一样大小的数组遍历一遍原数组数出来0、1、2的个数然后按照个数直接写入新数组。但题目要求在原地弄也就是不能通过我们这样拷贝的方式。并且进阶要求只遍历一遍。空间限制我们时间也限制我们那还怎么弄因为要么牺牲空间换时间要么牺牲时间换空间。他的要求不合理呀再仔细一看其实进阶要求的并不是时间复杂度在O(n)而是只遍历一遍。直觉就告诉我们遍历这一遍的时候必须狠狠折腾。法一三指针 可以不用看灵感来自于快排。从左到右遍历数组nums如果是0都放到左边如果是2都放到右边。维护两个指针一个left指向下一个放0的位置一个right指向下一个放2的位置。再用一个指针去遍历。遍历到第i个时有三种情况嘛分三种情况讨论。1. 当nums[i]0时放到左边去具体操作是把指针i和指针left指向的元素交换一下。① 重置left指针通过while循环重置left指针到下一个放0的位置。② 重置i指针因为新换到了i位置上一个数字所以下次还是遍历i位置所以i指针不变2. 当nums[i]1时继续遍历下一个。3. 当nums[i]2时放到右边去具体操作是把指针i和指针right指向的元素交换一下。① 重置right指针通过while循环重置right指针到下一个放2的位置。② 重置i指针因为新换到了i位置上一个数字所以下次还是遍历i位置所以i指针不变然后捏是通过用例测出来的一个特殊情况。会出现这样一种情况ileft且nums[i]nums[left]0这种情况就不要去交换了直接i和left都加一。PS 因为我们的left指针和i指针都是从左往右的嘛所以才会在交换0的时候遇到这种情况交换2的时候不存在这种情况。class Solution { public void sortColors(int[] nums) { //定义left指向下一个放0的位置 //定义right:指向下一个放2的位置 //定义i: 当前遍历的位置 int left0; int rightnums.length-1; while(leftnums.length nums[left]0) left; //初始化 while(right0 nums[right]2) right--; //初始化 int ileft; //初始化 while(iright){ if(nums[i]0){ if(ileft){left;i;} //出错案例测出来的情况 else{swap(nums,left,i); while(nums[left]0) left;} //因为新换到了i位置上一个数字所以下次还是遍历i位置所以i指针不变 } else if(nums[i]1){i;}//什么也不干直接遍历下一个 else if(nums[i]2){swap(nums,i,right);while(nums[right]2) right--;} } } public void swap(int[] nums,int a,int b){ int temp nums[a]; nums[a] nums[b]; nums[b] temp; } }法二三指针 这个写起来更好实现还有个更简单的思路同样也是三指针这次维护的是下一个放0的位置下一个放1的位置。同样也分三种情况1.nums[i]0时把这个0往前插zero和i之间的整体后移一位2.nums[i]1时把这个1往前插one和i之前的整体后移一位3. nums[i]2时继续遍历下一个class Solution { public void sortColors(int[] nums) { //定义zero下一个放0的位置 //定义one下一个放1的位置 //定义i当前遍历的位置 int zero0; while(zero nums.length nums[zero]0) zero; //初始化 int onezero; while(one nums.length nums[one]1) one; //初始化 int ione; //初始化 while (inums.length){ if(nums[i]0){ //[zero,i-1]闭区间内的元素整体后移一位 for(int ji;jzero;j--){nums[j]nums[j-1];} //插入0 nums[zero]0; //重置指针 zero; i; one; //坑在这里别忘了1的指针也跟着往右移了一位 } else if(nums[i]1){ //[one,i-1]闭区间内的元素整体后移一位 for(int ji;jone;j--){nums[j]nums[j-1];} //插入0 nums[one]1; //重置指针 one; i; } else if(nums[i]2) i; } } }
