Comment on page
659.Split-Array-into-Consecutive-Subsequences
Given an array nums sorted in ascending order, return true if and only if you can split it into 1 or more subsequences such that each subsequence consists of consecutive integers and has length at least 3.
Example 1:
Input: [1,2,3,3,4,5]
Output: True
Explanation:
You can split them into two consecutive subsequences :
1, 2, 3
3, 4, 5
Example 2:
Input: [1,2,3,3,4,4,5,5]
Output: True
Explanation:
You can split them into two consecutive subsequences :
1, 2, 3, 4, 5
3, 4, 5
Example 3:
Input: [1,2,3,4,4,5]
Output: False
Constraints:
1 <= nums.length <= 10000
public boolean isPossible(int[] nums) {
Map<Integer, Integer> freq = new HashMap<>(), appendfreq = new HashMap<>();
for (int i : nums) freq.put(i, freq.getOrDefault(i,0) + 1);
for (int i : nums) {
if (freq.get(i) == 0) continue;
else if (appendfreq.getOrDefault(i, 0) > 0) {
// freq[i]不为零，可以追加到子列
appendfreq.put(i, appendfreq.get(i) - 1);
appendfreq.put(i+1, appendfreq.getOrDefault(i+1,0) + 1);
}
else if (freq.getOrDefault(i+1,0) > 0 && freq.getOrDefault(i+2,0) > 0) { // 创建新的连续子列
freq.put(i+1, freq.get(i+1) - 1);
freq.put(i+2, freq.get(i+2) - 1);
appendfreq.put(i+3, appendfreq.getOrDefault(i+3,0) + 1);
}
else return false; // 单个数字，直接返回
freq.put(i, freq.get(i) - 1);
}
return true;
}
Say we have a count of each number, and let
tails[x] be the number of chains ending right before x.Time: O(N) && Space: O(N)
class Solution {
public boolean isPossible(int[] nums) {
Counter count = new Counter();
Counter tails = new Counter();
for (int x: nums) count.add(x, 1);
for (int x: nums) {
if (count.get(x) == 0) {
continue;
} else if (tails.get(x) > 0) {
tails.add(x, -1);
tails.add(x+1, 1);
} else if (count.get(x+1) > 0 && count.get(x+2) > 0) {
count.add(x+1, -1);
count.add(x+2, -1);
tails.add(x+3, 1);
} else {
return false;
}
count.add(x, -1);
}
return true;
}
}
class Counter extends HashMap<Integer, Integer> {
public int get(int k) {
return containsKey(k) ? super.get(k) : 0;
}
public void add(int k, int v) {
put(k, get(k) + v);
}
}
Time: O(N) && Space: O(N)
class Solution {
public boolean isPossible(int[] nums) {
Integer prev = null;
int prevCount = 0;
Queue<Integer> starts = new LinkedList();
int anchor = 0;
for (int i = 0; i < nums.length; i++) {
int t = nums[i];
if (i == nums.length - 1 || nums[i+1] != t) {
int count = i - anchor + 1;
if (prev != null && t - prev != 1) {
while (prevCount-- > 0) {
if (prev < starts.poll() + 2) return false;
prev = null;
}
}
if (prev == null || t - prev == 1) {
while (prevCount > count) {
prevCount--;
if (t-1 < starts.poll() + 2) return false;
}
while (prevCount++ < count) {
starts.add(t);
}
}
prev = t;
preCount = count;
anchor = i + 1;
}
}
while (prevCount-- > 0) {
if (nums[nums.length - 1] < starts.poll() + 2) return false;
}
return true;
}
}
Last modified 2yr ago