【贪心】【哈希】个人练习-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);
                }
                else
                    return false;
            }
        }
        return true;
    }
};

原文地址：https://blog.csdn.net/Rstln/article/details/143644213

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！