75. 颜色分类

思路：

• 看到这样的按数字分类，第一时间感觉应该用排序，这样的话就直接按大小分好了。但是要求不用排序，且一遍扫描，就算了。
• 第二种思路： 基本思路：定义俩数字，0值的最右位置zero，以及2值最左位置tow 使得，[0, zero] = 0， (zero, i) = 1，(two, len - 1] = 2，剩下的就是把数字按这个排了
• 第三种思路： 赋值法，假定所有数字都是2；然后对0和1数字进行计数和赋值；

代码2：

代码语言：javascript复制

  class Solution {
        public void sortColors(int[] nums) {
            int len = nums.length;
            if (nums.length < 2) {
                return;
            }
            //按照0，1，2顺序排序
            int zero = -1;
            int two = len;
            int i = 0;
            while (i<two){
                if (nums[i]==0){
                    //之前的数字要么是0，要么是1，不会是2，因此不需要再考虑当前数字要不要再次交换问题，因此直接i  
                    swap(nums,  zero,i  );
                }else if (nums[i]==2){
                    //由于从后面交换到前面的数字，情况无法保证是否需要再次交换，因此需要再次遍历
                    swap(nums,--two,i);
                }else {
                    i  ;
                }
            }
        }

        private void swap(int[] nums, int index1, int index2) {
            int temp = nums[index1];
            nums[index1] = nums[index2];
            nums[index2] = temp;
        }
    }

思路3代码：

代码语言：javascript复制

 public void sortColors(int[] nums) {
            //0的数量，小于等于1的数量
            int count0=0,count1=0;
            for (int i = 0; i < nums.length; i  ) {
                int curr=nums[i];
                nums[i]=2;
                if (curr<2){
                    nums[count1  ]=1;
                }
                if (curr<1){
                    nums[count0  ]=0;
                }
            }
        }

zero 排序

0 人点赞