一、Problem

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 possible otherwise return False.

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].

二、Solution

方法一：排序

• 用 map 统计数字的频次，并对数组 A 排序，排序的好处是在枚举完一个以 A[i] 为开头且大小为 k 的区间后，可以立马得到一个比 A[i] 大且最小的数字。
• 贪心思路：如果一个一 A[i] 为开头的区间能组成大小为 k 的连续数集合，那么在 map 中一定可以找到 $[A[i]+1, A[i]+2,..., A[i]+k]$ $ 的全部数字。

这题做得比较急：导致使用 A[i] 后忘记删去 A[i] 的使用频次了，浪费了一点时间…

class Solution {public boolean isPossibleDivide(int[] A, int k) {int n = A.length;if (n % k != 0)return false;Map<Integer, Integer> m = new HashMap<>();Arrays.sort(A);for (int i : A)  m.put(i, m.getOrDefault(i, 0) + 1);int cnt = 0, need = n / k;for (int i : A) {int fr = m.get(i);if (fr == 0)continue;m.put(i, fr-1);for (int j = 1; j < k; j++) {int freq = m.getOrDefault(i+j, 0);if (freq == 0)return false;m.put(i+j, freq - 1);}if (++cnt == need)return true;}return true;}
}

复杂度分析

• 时间复杂度：$O(nlogn)$，
• 空间复杂度：$O(n)$，