将数组划分成连续子序列 Split Array into Consecutive Subsequences

时间:2021-08-30 19:39:46

2018-08-04 20:47:43

问题描述:

将数组划分成连续子序列 Split Array into Consecutive Subsequences

问题描述:

本题需要的是将一个数组划分成子序列,保证每个子序列是连续的,并且长度要大于等于3。

解题思路是使用贪心算法,首先对数组中的数字进行计数,然后遍历数组,对每个数字,如果说candidate中有这个数字,那么意味着它可以和之前的子序列组成更长的序列,直接将之添加到先前的子序列中即可。如果说candidate中没有当前的数字,那么当前的数字只能作为序列的首数字出现。如果这两个都不满足,那么直接判false。

    public boolean isPossible(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
Map<Integer, Integer> candidate = new HashMap<>();
for (int i : nums) map.put(i, map.getOrDefault(i, 0) + 1);
for (int i = 0; i < nums.length; i++) {
if (map.get(nums[i]) == 0) continue;
if (candidate.getOrDefault(nums[i], 0) > 0) {
candidate.put(nums[i], candidate.get(nums[i]) - 1);
candidate.put(nums[i] + 1, candidate.getOrDefault(nums[i] + 1, 0) + 1);
}
else if (map.getOrDefault(nums[i] + 1, 0) > 0 && map.getOrDefault(nums[i] + 2, 0) > 0) {
map.put(nums[i] + 1, map.get(nums[i] + 1) - 1);
map.put(nums[i] + 2, map.get(nums[i] + 2) - 1);
candidate.put(nums[i] + 3, candidate.getOrDefault(nums[i] + 3, 0) + 1);
}
else return false;
map.put(nums[i], map.get(nums[i]) - 1);
}
return true;
}