嗨客网搜索
颜色分类

描述

力扣第 75 题。给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。

此题中,我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

示例 1:

输入:nums = [2,0,2,1,1,0] 输出:[0,0,1,1,2,2]

示例 2:

输入:nums = [2,0,1] 输出:[0,1,2]

示例3:

输入:nums = [0] 输出:[0]

示例4:

输入:nums = [1] 输出:[1]

提示:

  • n == nums.length
  • 1 <= n <= 300
  • nums[i] 为 0、1 或 2

思路

该题虽然是一个场景题目,实际上抛开该场景,就是对一个数组进行排序。数组里面的元素为 0,1,2。它们的顺序是乱的,需要按照 0,1,2 的方式输出。我们可以考虑使用冒泡排序法来将数组数据排序,冒泡排序的基本思路是将数组中的两个相邻的数据进行比较,如果两个元素反序,就将两个元素换位置,直到遍历到最后没有反序为止。它就像鱼吐泡泡一样,每次得到最大值。

01_冒泡排序.png

我们以示例1为实例来进行判断,如下:

02 颜色分类.png

第一轮排序的时候顺序如下:

  1. 2 和 0 比较,2 比 0 大,需要和 0 换位置。

03 颜色分类.png

  1. 2 和 2 比较,2 和 2 相等,所以不需要换位置。

  2. 2 和 1 比较,由于 2 比 1 大,需要将 2 和 1 换位置

04 颜色分类.png

  1. 2 继续和 1 比较,2 比 1 大,将 2 和 1 交换位置

05 颜色分类.png

  1. 将 2 和 0 比较,2 比 0 大,所以将 2 和 0 交换位置

06 颜色分类.png

第一轮遍历全部完成,得到如下结果:

07 颜色分类.png

剩下的元素按照上面的流程进行比较,得到如下结果:

08 颜色分类.png

代码具体实现

Java语言版本

class Solution { public void sortColors(int[] nums) { for(int i = 0;i< nums.length - 1 ;i++){ boolean isSorted = true; for(int j =0;j<nums.length - i - 1;j++){ int tmp = 0; if(nums[j] > nums[j + 1]){ tmp = nums[j]; nums[j] = nums[j + 1]; nums[j+1] = tmp; isSorted = false; } } if(isSorted){ break; } } } }

Go语言版本

func sortColors(nums []int) { for i := 0;i< len(nums) - 1 ;i++ { isSorted := true; for j := 0;j<len(nums) - i - 1;j++ { tmp := 0 if nums[j] > nums[j + 1] { tmp = nums[j] nums[j] = nums[j + 1] nums[j+1] = tmp isSorted = false } } if(isSorted){ break } } }

赞助商链接:


嗨客网顶部