Given an array of integers nums and a positive integer k, find whether it’s possible to divide this array into sets of k consecutive numbers
Return True if its possibleotherwise return False.
Example 1:
Input: nums = [1,2,3,3,4,4,5,6], k = 4 Output: true Explanation: Array can be divided into [1,2,3,4] and [3,4,5,6].
Example 2:
Input: nums = [3,2,1,2,3,4,3,4,5,9,10,11], k = 3 Output: true Explanation: Array can be divided into [1,2,3] , [2,3,4] , [3,4,5] and [9,10,11].
Example 3:
Input: nums = [3,3,2,2,1,1], k = 3 Output: true
Example 4:
Input: nums = [1,2,3,4], k = 3 Output: false Explanation: Each array should be divided in subarrays of size 3.
Constraints:
1 <= nums.length <= 10^51 <= nums[i] <= 10^91 <= k <= nums.length
Solution: BST + Greedy
Start from the smallest available number and find k consecutive numbers.
Time complexity: O(nlogn)
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
// Author: Huahua class Solution { public: bool isPossibleDivide(vector<int>& nums, int k) { if (nums.size() % k) return false; map<int, int> m; for (int num : nums) ++m[num]; while (m.size()) { const int s = m.cbegin()->first; for (int i = 0; i < k; ++i) { auto it = m.find(s + i); if (it == m.cend()) return false; if (--it->second == 0) m.erase(it); } } return true; } }; |
C++/V2
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
// Author: Huahua class Solution { public: bool isPossibleDivide(vector<int>& nums, int k) { if (nums.size() % k) return false; map<int, int> m; for (int num : nums) ++m[num]; while (m.size()) { auto it = m.begin(); const int s = it->first; for (int i = 0; i < k; ++i, ++it) { if (it->first != s + i) return false; if (--it->second == 0) m.erase(it); } } return true; } }; |
Solution 2: HashTable
Time complexity: O(n)
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
class Solution { public: bool isPossibleDivide(vector<int>& nums, int k) { if (nums.size() % k) return false; unordered_map<int, int> m; for (int num : nums) ++m[num]; queue<int> starts; for (auto [n, f] : m) if (!m.count(n - 1)) starts.push(n); while (!starts.empty()) { int s = starts.front(); starts.pop(); for (int t = s + k - 1; t >= s; t--) { if (m[t] < m[s]) return false; if ((m[t] -= m[s]) == 0) { m.erase(t); if (m.count(t + 1)) starts.push(t + 1); } } } return true; } }; |
Related Problems
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment