我要招人

去企业版

首页 > 试题广场 >

颜色分类

[编程题]颜色分类

热度指数：2172 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个包含红色，白色，蓝色，一同 n 个元素的数组，对其进行排序使得相同的颜色相邻并且按照红色，白色，蓝色的顺序排序。

数组中 0 代表红色，1 代表白色，2 代表蓝色。

数据范围： $1 \le n \le 100 \$ ，数组中只包含 0 1 2。

示例1

输入

[0,2,1]

输出

[0,1,2]

示例2

输入

[0,0,2,0]

输出

[0,0,0,2]

算法知识视频讲解

Java

pein531

荷兰国旗问题，使用快排中的partition过程来解决，原问题可以描述为：将把小于1的数放在左边，等于1的数放在中间，大于1的数放在右边。构建两个指针less和more，分别表示小于区域的右边界和大于区域的左边界，初始为-1和colors.length。从cur=0的位置开始，然后进行如下的partition过程：

如果colors[cur]<1，就将当前的数与小于区的下一个数交换，即less自增后将colors[cur]放在less位置，小于区域扩大了1个位置，并右移cur指针考察下一个数。
如果colors[cur]>1，就将当前的数与大于区的前一个位置交换，即more自减后将colors[cur]放在more位置，大于区扩大一个位置，但此时并不移动cur指针，因为还没有考察从后面换过来的这个数是否还要往前换（换过来的如果是0就还得往前换）。
如果colors[cur]=1，直接右移cur指针。

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param colors int整型一维数组 
     * @return int整型一维数组
     */
    public int[] sortColor (int[] colors) {
        // write code here
        int less = -1, more = colors.length;
        int cur = less + 1;
        while(cur < more){
            if(colors[cur] < 1){
                swap(colors, ++less, cur++);
            }else if(colors[cur] > 1){
                swap(colors, --more, cur);
            }else{
                cur++;
            }
        }
        return colors;
    }
    
    private void swap(int[] arr, int i, int j) {
        if(i != j){
            arr[i] = arr[i] ^ arr[j];
            arr[j] = arr[i] ^ arr[j];
            arr[i] = arr[i] ^ arr[j];
        }
    }
}

发表于 2021-12-12 17:59:21 回复(0)

Java

世界杯2009

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param colors int整型一维数组 
     * @return int整型一维数组
     */
    public int[] sortColor(int[] colors) {
        // write code here
        Arrays.sort(colors);
        return colors;
    }

}

发表于 2022-04-14 22:55:38 回复(0)

C++

牛客362459853号

我都不知道这个题目有什么意思，直接就是一个sort（）函数就完事了。

发表于 2021-11-24 16:24:53 回复(1)

小谷围做题家

package main
import "sort"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param colors int整型一维数组 
 * @return int整型一维数组
*/
func sortColor( colors []int ) []int {
    sort.Ints(colors)
    return colors
}

发表于 2023-03-09 00:30:51 回复(0)

Java

輝长六加1

统计三种颜色个数（或者统计前两种即可），类似计数排序

import java.util.*;
public class Solution {
  public int[] sortColor (int[] colors) {
      if (null == colors) {
          return new int[]{};
      }

      // 记住0，1的数量，剩下的元素肯定都是2，因此不用统计2
      int count0 = 0, count1 = 0;
      // 统计前两种颜色出现次数
      for (int color : colors) {
          if (color == 0) {
              count0++;
          } else if (color == 1) {
              count1++;
          }
      }

      // 根据三种颜色的数量依次排序
      for (int i = 0;i < colors.length;i++) {
          if (count0 != 0) {
              colors[i] = 0;
              count0--;
          } else if (count1 != 0) {
              colors[i] = 1;
              count1--;
          } else {
              colors[i] = 2;
          }
      }

      return colors;
  }
}

发表于 2022-04-20 14:55:29 回复(0)

Java

除了吃还会干嘛

public int[] sortColor (int[] colors) {
        // write code here
        /*int length = colors.length;
        Stack<Integer> stack0 = new Stack<Integer>();
        Stack<Integer> stack1 = new Stack<Integer>();
        Stack<Integer> stack2 = new Stack<Integer>();
        for (int i = 0; i < length; i++) {
            if (colors[i]==0){
                stack0.add(colors[i]);
            } else if (colors[i]==1){
                stack1.add(colors[i]);
            } else if (colors[i]==2){
                stack2.add(colors[i]);
            }
        }
        int[] ints = new int[length];
        int i =0;
        while(!stack0.isEmpty()){
            ints[i]=stack0.pop();
            i++;
        }
        while(!stack1.isEmpty()){
            ints[i]=stack1.pop();
            i++;
        }
        while(!stack2.isEmpty()){
            ints[i]=stack2.pop();
            i++;
        }
        return ints;*/
        int length = colors.length;
        int m = 0;
        int n = 0;

        for (int color : colors) {
            if (color == 0){
                m++;
            }
            if (color == 1){
                n++;
            }
        }
        int[] ints = new int[length];
        for (int i = 0; i < length; i++) {
            if (i<m){
                ints[i] = 0;
            } else if (m<=i && i<m+n){
                ints[i] = 1;
            } else {
                ints[i] = 2;
            }
        }
        return ints;
    }

发表于 2022-01-29 15:31:44 回复(0)

Java

牛客196305255号

public int[] sortColor (int[] colors) {
        int arr[]=new int[colors.length];
        int start=0;
        int end=arr.length-1;
        for(int color:colors) {
        	if(color==0)
        		arr[start++]=0;
        	else if(color==2)
        		arr[end--]=2;
        }
        for(int i=start;i<=end;i++)
        	arr[i]=1;
        return arr;
    }

发表于 2022-01-02 20:33:26 回复(0)