【贪心】【哈希】个人练习-Leetcode-1296. Divide Array in Sets of K Consecutive Numbers

题目链接：https://leetcode.cn/problems/divide-array-in-sets-of-k-consecutive-numbers/description/

题目大意：给出一个数组nums[]和一个数k，求nums[]能否被分成若干个k个元素的连续的子列。

思路：比较简单，贪心就行，找到当前剩下的元素中最小的v，然后（如果合法）它必然属于某个子列，那么就找v+1, ..., v+k-1，这些元素的剩余量都减1即可。如果出现空缺，那么就返回false。

很显然用哈希表比较合适。不过我开始做时，因为要从小到大遍历剩余元素，就用了map<int, int>，直接从map的头开始遍历。虽然通过了，但速度有点慢。看了题解，发现用的是unordered_map<int, int>，区别就是先把nums[]排序了一遍，然后对nums[]进行遍历。这也是OK的，因为排序后，nums[]中，每个最小的元素都需要被归入一个子列中。这样就节约了时间。

完整代码

class Solution {
public:bool isPossibleDivide(vector<int>& nums, int k) {int n = nums.size();if (n % k)return false;sort(nums.begin(), nums.end());unordered_map<int, int> cnt;for (auto& num : nums) {cnt[num]++;}for (auto& num : nums) {if (!cnt.count(num))continue;cnt[num]--;if (cnt[num] == 0)cnt.erase(num);for (int i = 1; i < k; i++) {if (cnt.count(num+i) != 0) {cnt[num+i]--;if (cnt[num+i] == 0)cnt.erase(num+i);}elsereturn false;}}return true;}
};