划分数组为连续数字的集合
难度:
标签:
题目描述
代码结果
运行时间: 107 ms, 内存: 31.7 MB
/*
题目思路:
1. 首先,我们可以使用一个 TreeMap 来记录每个数字的出现次数,这样可以保证我们可以按顺序访问每个数字。
2. 使用 Java Stream API 来进行更简洁的处理和遍历。
3. 然后,我们遍历 TreeMap 中的每个数字,如果当前数字的次数大于 0,
则我们尝试构建一个长度为 k 的连续子序列,子序列中的每个数字的次数必须足够。
4. 如果无法构建这样的子序列,则返回 false,否则将子序列中的每个数字的次数减少。
5. 如果成功遍历整个 TreeMap 并且没有失败,则返回 true。
*/
import java.util.*;
import java.util.stream.*;
public class Solution {
public boolean isPossibleDivide(int[] nums, int k) {
if (nums.length % k != 0) return false;
Map<Integer, Long> countMap = Arrays.stream(nums)
.boxed()
.collect(Collectors.groupingBy(e -> e, TreeMap::new, Collectors.counting()));
for (int num : countMap.keySet()) {
long count = countMap.get(num);
if (count > 0) {
for (int i = 1; i < k; i++) {
if (countMap.getOrDefault(num + i, 0L) < count) {
return false;
}
countMap.put(num + i, countMap.get(num + i) - count);
}
}
}
return true;
}
}
解释
方法:
此题解采用的方法是首先统计数组中每个数字出现的次数,存储在一个哈希表中。然后,对哈希表的键(即数字)进行排序,以保证从最小的数字开始处理。对每个数字,如果它还未完全用于构成之前的连续子集,会尝试构造以该数字为起点,长度为 k 的连续数字子集。每次尝试减去相应数量,如果在此过程中发现某个数字不足以形成连续子集,直接返回 False。如果能成功构造出所有连续子集,则返回 True。
时间复杂度:
O(n + u log u + nk)
空间复杂度:
O(n)
代码细节讲解
🦆
为什么在处理哈希表键时需要先进行排序?
▷🦆
在构造连续子集时,如果`nums_count[i+key]`的值已经为0,为什么还需要继续检查后续的数字?
▷🦆
哈希表更新`nums_count[i+key]-=value`时,如果减去的value大于实际存在的数量,这种情况是如何被处理的?
▷🦆
算法在遇到无法构成序列的情况时直接返回False,这种实现方式是否考虑了所有可能的边界条件?
▷