75. 颜色分类

名字是乱打的

发布于 2021-12-23 18:52:39

3910

文章被收录于专栏：软件工程软件工程

思路：

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

代码2：

  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代码：

 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;
                }
            }
        }