【LeeCode】颜色分类

【LeeCode】颜色分类

【题目描述】

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、 蓝色顺序排列。此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

注意:   不能使用代码库中的排序函数来解决这道题。

【示例】

输入: [2,0,2,1,1,0]

输出: [0,0,1,1,2,2]

【代码】

package com.company;import java.util.Arrays;public class Solution { public static void main(String[] args) { int[] arr = {2, 2, 0, 1, 1, 0}; chuli(arr); chuli2(arr); chuli3(arr); } // 方案3： // 定义一个指针，记录数组开头0的个数，然后遍历数组，将0移到数组开头， // 当所有的0都放到数组前面后，然后再把1移到0后面 private static void chuli3(int[] arr) { // 定义left和righ分别指向左右位置 int left = 0; int right = arr.length - 1; // 处理为0的数字 for(int i = 0; i <= right; i++){ // 当前值为0,但索引不是left， 交换位置 if(arr[i] == 0 && i != left){ int tmp = arr[i]; arr[i] = arr[left]; arr[left] = tmp; left++; }else if(arr[i] == 0){ left++; } // 处理为2的数字 if(arr[i] == 2 && arr[right] == 2){ } } } // 方案2：统计0,1,2出现的次数, 然后依次输出即可 private static void chuli2(int[] arr) { int a = 0; int b = 0; int c = 0; for(int i = 0; i < arr.length; i++){ if(arr[i] == 0 ){ a++; }else if(arr[i] == 1){ b++; }else { c++; } } for(int i = 0; i < a; i++){ arr[i] = 0; } // 注意： 这里输出是从a开始的，a+b结束 for(int i = a; i < a + b; i++){ arr[i] = 1; } for(int i = a + b; i < a + b + c; i++){ arr[i] = 2; } for(int x: arr){ System.out.print(x + " "); } } // 方案1： 使用排序算法排序即可 这里使用选择排序 private static void chuli(int[] arr) { for(int i = 0; i < arr.length; i++){ for(int j = i + 1; j < arr.length; j++){ if(arr[i] > arr[j]){ int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } } } System.out.println(Arrays.toString(arr)); }}

【学习参考】

https://blog.csdn-/weixin_37850160/article/details/87988889

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。