给定一个包含红色,白色,蓝色,一同 n 个元素的数组,对其进行排序使得相同的颜色相邻并且按照 红色,白色,蓝色的顺序排序。
数组中 0 代表红色,1 代表白色,2 代表蓝色。
数据范围: , 数组中只包含 0 1 2。
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]; } } }
统计三种颜色个数(或者统计前两种即可),类似计数排序
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; } }
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; }
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; }