LeetCode -Hot100 -75. 颜色分类

前言

本专栏主要通过“LeetCode 热题100”，来捡起自己本科阶段的算法知识与技巧。语言主要使用c++/java。如果同样正在练习LeetCode 热题100的朋友欢迎关注或订阅本专栏。有疑问欢迎留言交流~

题目描述

题目链接

给定一个包含红色、白色和蓝色、共 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]

思路

这个题目被leetcode归类为技巧专栏里面。**题目是一个典型的“假排序”问题。**题目的背景虽然是说的排序，但是其实压根不用真的去排序，只需要记录每个元素出现的个数即可。

记得本科做算法训练也出现过这类题目。要排序的数组很大，即便是O(nlog(n))也无法满足要求。但是它给的数字本身值的范围很小，技巧和本题一摸一样。

本题代码如下：

class Solution {
public:void sortColors(vector<int>& nums) {//经典的“假排序”(只需要记录出现的次数)unordered_map<int,int> numCount;for(int num:nums){numCount[num]++;}//放0int curi = 0;while(numCount[0]--){nums[curi++] = 0;}//放1while(numCount[1]--){nums[curi++] = 1;}//放2while(numCount[2]--){nums[curi++] = 2;}}
};