class Solution {
public:
bool isPossible(vector<int>& nums) {
}
};
659. 分割数组为连续子序列
给你一个按升序排序的整数数组 num（可能包含重复数字），请你将它们分割成一个或多个长度至少为 3 的子序列，其中每个子序列都由连续整数组成。
如果可以完成上述分割，则返回 true ；否则，返回 false 。
示例 1：
输入: [1,2,3,3,4,5] 输出: True 解释: 你可以分割出这样两个连续子序列 : 1, 2, 3 3, 4, 5
示例 2：
输入: [1,2,3,3,4,4,5,5] 输出: True 解释: 你可以分割出这样两个连续子序列 : 1, 2, 3, 4, 5 3, 4, 5
示例 3：
输入: [1,2,3,4,4,5] 输出: False
提示：
1 <= nums.length <= 10000相似题目
原站题解
java 解法, 执行用时: 25 ms, 内存消耗: 42.5 MB, 提交时间: 2022-12-12 14:38:08
class Solution {
public boolean isPossible(int[] nums) {
Map<Integer, Integer> countMap = new HashMap<Integer, Integer>();
Map<Integer, Integer> endMap = new HashMap<Integer, Integer>();
for (int x : nums) {
int count = countMap.getOrDefault(x, 0) + 1;
countMap.put(x, count);
}
for (int x : nums) {
int count = countMap.getOrDefault(x, 0);
if (count > 0) {
int prevEndCount = endMap.getOrDefault(x - 1, 0);
if (prevEndCount > 0) {
countMap.put(x, count - 1);
endMap.put(x - 1, prevEndCount - 1);
endMap.put(x, endMap.getOrDefault(x, 0) + 1);
} else {
int count1 = countMap.getOrDefault(x + 1, 0);
int count2 = countMap.getOrDefault(x + 2, 0);
if (count1 > 0 && count2 > 0) {
countMap.put(x, count - 1);
countMap.put(x + 1, count1 - 1);
countMap.put(x + 2, count2 - 1);
endMap.put(x + 2, endMap.getOrDefault(x + 2, 0) + 1);
} else {
return false;
}
}
}
}
return true;
}
}
javascript 解法, 执行用时: 92 ms, 内存消耗: 49.3 MB, 提交时间: 2022-12-12 14:37:48
/**
* @param {number[]} nums
* @return {boolean}
*/
var isPossible = function(nums) {
const countMap = new Map();
const endMap = new Map();
for (const x of nums) {
const count = (countMap.get(x) || 0) + 1;
countMap.set(x, count);
}
for (const x of nums) {
const count = countMap.get(x) || 0;
if (count > 0) {
const prevEndCount = endMap.get(x - 1) || 0;
if (prevEndCount > 0) {
countMap.set(x, count - 1);
endMap.set(x - 1, prevEndCount - 1);
endMap.set(x, (endMap.get(x, 0) || 0) + 1);
} else {
const count1 = countMap.get(x + 1, 0);
const count2 = countMap.get(x + 2, 0);
if (count1 > 0 && count2 > 0) {
countMap.set(x, count - 1);
countMap.set(x + 1, count1 - 1);
countMap.set(x + 2, count2 - 1);
endMap.set(x + 2, (endMap.get(x + 2) || 0) + 1);
} else {
return false;
}
}
}
}
return true;
};
python3 解法, 执行用时: 88 ms, 内存消耗: 15.9 MB, 提交时间: 2022-12-12 14:37:34
class Solution:
def isPossible(self, nums: List[int]) -> bool:
countMap = collections.Counter(nums)
endMap = collections.Counter()
for x in nums:
if (count := countMap[x]) > 0:
if (prevEndCount := endMap.get(x - 1, 0)) > 0:
countMap[x] -= 1
endMap[x - 1] = prevEndCount - 1
endMap[x] += 1
else:
if (count1 := countMap.get(x + 1, 0)) > 0 and (count2 := countMap.get(x + 2, 0)) > 0:
countMap[x] -= 1
countMap[x + 1] -= 1
countMap[x + 2] -= 1
endMap[x + 2] += 1
else:
return False
return True
golang 解法, 执行用时: 72 ms, 内存消耗: 6.8 MB, 提交时间: 2022-12-12 14:37:21
// 贪心
func isPossible(nums []int) bool {
left := map[int]int{} // 每个数字的剩余个数
for _, v := range nums {
left[v]++
}
endCnt := map[int]int{} // 以某个数字结尾的连续子序列的个数
for _, v := range nums {
if left[v] == 0 {
continue
}
if endCnt[v-1] > 0 { // 若存在以 v-1 结尾的连续子序列，则将 v 加到其末尾
left[v]--
endCnt[v-1]--
endCnt[v]++
} else if left[v+1] > 0 && left[v+2] > 0 { // 否则，生成一个长度为 3 的连续子序列
left[v]--
left[v+1]--
left[v+2]--
endCnt[v+2]++
} else { // 无法生成
return false
}
}
return true
}
golang 解法, 执行用时: 120 ms, 内存消耗: 6.9 MB, 提交时间: 2022-12-12 14:36:50
type hp struct{ sort.IntSlice }
func (h *hp) Push(v interface{}) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() interface{} { a := h.IntSlice; v := a[len(a)-1]; h.IntSlice = a[:len(a)-1]; return v }
func (h *hp) push(v int) { heap.Push(h, v) }
func (h *hp) pop() int { return heap.Pop(h).(int) }
func isPossible(nums []int) bool {
lens := map[int]*hp{}
for _, v := range nums {
if lens[v] == nil {
lens[v] = new(hp)
}
if h := lens[v-1]; h != nil {
prevLen := h.pop()
if h.Len() == 0 {
delete(lens, v-1)
}
lens[v].push(prevLen + 1)
} else {
lens[v].push(1)
}
}
for _, h := range lens {
if h.IntSlice[0] < 3 {
return false
}
}
return true
}
python3 解法, 执行用时: 172 ms, 内存消耗: 15.9 MB, 提交时间: 2022-12-12 14:36:29
class Solution:
def isPossible(self, nums: List[int]) -> bool:
mp = collections.defaultdict(list)
for x in nums:
if queue := mp.get(x - 1):
prevLength = heapq.heappop(queue)
heapq.heappush(mp[x], prevLength + 1)
else:
heapq.heappush(mp[x], 1)
return not any(queue and queue[0] < 3 for queue in mp.values())
javascript 解法, 执行用时: 176 ms, 内存消耗: 50.3 MB, 提交时间: 2022-12-12 14:35:32
/**
* @param {number[]} nums
* @return {boolean}
*/
var isPossible = function(nums) {
const map = new Map();
for (let x of nums) {
if (!map.has(x)) {
map.set(x, new MinPriorityQueue());
}
if (map.has(x - 1)) {
const prevLength = map.get(x - 1).dequeue()['priority'];
if (map.get(x - 1).isEmpty()) {
map.delete(x - 1);
}
map.get(x).enqueue(x, prevLength + 1);
} else {
map.get(x).enqueue(x, 1);
}
}
for (let [key, value] of map.entries()) {
if (value.front()['priority'] < 3) {
return false;
}
}
return true;
};
java 解法, 执行用时: 65 ms, 内存消耗: 42.4 MB, 提交时间: 2022-12-12 14:35:12
class Solution {
public boolean isPossible(int[] nums) {
Map<Integer, PriorityQueue<Integer>> map = new HashMap<Integer, PriorityQueue<Integer>>();
for (int x : nums) {
if (!map.containsKey(x)) {
map.put(x, new PriorityQueue<Integer>());
}
if (map.containsKey(x - 1)) {
int prevLength = map.get(x - 1).poll();
if (map.get(x - 1).isEmpty()) {
map.remove(x - 1);
}
map.get(x).offer(prevLength + 1);
} else {
map.get(x).offer(1);
}
}
Set<Map.Entry<Integer, PriorityQueue<Integer>>> entrySet = map.entrySet();
for (Map.Entry<Integer, PriorityQueue<Integer>> entry : entrySet) {
PriorityQueue<Integer> queue = entry.getValue();
if (queue.peek() < 3) {
return false;
}
}
return true;
}
}