青岛制作网站哪家公司好,网络推广与优化,应用市场最新版下载,python基础教程第二版题目链接#xff1a;https://leetcode.cn/problems/divide-array-in-sets-of-k-consecutive-numbers/description/
题目大意#xff1a;给出一个数组nums[]和一个数k#xff0c;求nums[]能否被分成若干个k个元素的连续的子列。
思路#xff1a;比较简单#xff0c;贪心就…题目链接https://leetcode.cn/problems/divide-array-in-sets-of-k-consecutive-numbers/description/
题目大意给出一个数组nums[]和一个数k求nums[]能否被分成若干个k个元素的连续的子列。
思路比较简单贪心就行找到当前剩下的元素中最小的v然后如果合法它必然属于某个子列那么就找v1, ..., vk-1这些元素的剩余量都减1即可。如果出现空缺那么就返回false。
很显然用哈希表比较合适。不过我开始做时因为要从小到大遍历剩余元素就用了mapint, int直接从map的头开始遍历。虽然通过了但速度有点慢。看了题解发现用的是unordered_mapint, int区别就是先把nums[]排序了一遍然后对nums[]进行遍历。这也是OK的因为排序后nums[]中每个最小的元素都需要被归入一个子列中。这样就节约了时间。
完整代码
class Solution {
public:bool isPossibleDivide(vectorint nums, int k) {int n nums.size();if (n % k)return false;sort(nums.begin(), nums.end());unordered_mapint, 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(numi) ! 0) {cnt[numi]--;if (cnt[numi] 0)cnt.erase(numi);}elsereturn false;}}return true;}
};
