LeetCode力扣 75. 颜色分类 冒泡排序法，计数法

75. 颜色分类

难度中等1190收藏分享切换为英文接收动态反馈

给定一个包含红色、白色和蓝色、共 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.length
• 1 <= n <= 300
• nums[i] 为 0、1 或 2

法一：冒泡排序法

• class Solution {
      public void sortColors(int[] nums) {
  for(int i=nums.length-1;i>=0;i--){
                  for(int k=0;k<i;k++){
                      if(nums[k]>nums[k+1]){
                      int temp=nums[k+1];
                      nums[k+1]=nums[k];
                      nums[k]=temp;
                  }
                  
              }
          }
  
  
      }
  }

  

• 法二：计数法

  class Solution {
      public void sortColors(int[] nums) {
          
          int count0 = 0;
          int count1 = 0;
          int count2 = 0;
          //统计数组中每个数字个数
          for (int i = 0; i < nums.length; i++) {
  
              if (nums[i] == 0) {
                  count0++;
              } else if (nums[i] == 1) {
                  count1++;
              } else {
                  count2++;
              }
          }
          //根据之前统计值依次为数组赋值
          for (int i = 0; i < nums.length; i++) {
              if (count0 > 0) {
                  nums[i] = 0;
                  count0--;
              } else if (count1 > 0) {
                  nums[i] = 1;
                  count1--;
              } else {
                  nums[i] = 2;
              }
  
  
          }
  
      }
  }