split-array-into-consecutive-subsequences

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given an integer array <code>nums</code> that is sorted in non-decreasing order.

Determine if it is possible to split <code>nums</code> into one or more subsequences such that both of the following conditions are true:

<ul>
	<li>Each subsequence is a consecutive increasing sequence (i.e. each integer is exactly one more than the previous integer).</li>
	<li>All subsequences have a length of <code>3</code> or more.</li>
</ul>

Return <code>true</code> if you can split <code>nums</code> according to the above conditions, or <code>false</code> otherwise.

A subsequence of an array is a new array that is formed from the original array by deleting some (can be none) of the elements without disturbing the relative positions of the remaining elements. (i.e., <code>[1,3,5]</code> is a subsequence of <code>[1,2,3,4,5]</code> while <code>[1,3,2]</code> is not).

&nbsp;
Example 1:

<pre>
Input: nums = [1,2,3,3,4,5]
Output: true
Explanation: nums can be split into the following subsequences:
[1,2,3,3,4,5] --&gt; 1, 2, 3
[1,2,3,3,4,5] --&gt; 3, 4, 5
</pre>

Example 2:

<pre>
Input: nums = [1,2,3,3,4,4,5,5]
Output: true
Explanation: nums can be split into the following subsequences:
[1,2,3,3,4,4,5,5] --&gt; 1, 2, 3, 4, 5
[1,2,3,3,4,4,5,5] --&gt; 3, 4, 5
</pre>

Example 3:

<pre>
Input: nums = [1,2,3,4,4,5]
Output: false
Explanation: It is impossible to split nums into consecutive increasing subsequences of length 3 or more.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= nums.length &lt;= 104</code></li>
	<li><code>-1000 &lt;= nums[i] &lt;= 1000</code></li>
	<li><code>nums</code> is sorted in non-decreasing order.</li>
</ul>

isPossible

Split Array into Consecutive Subsequences

Top K Frequent Elements

top-k-frequent-elements

前 K 个高频元素

Divide Array in Sets of K Consecutive Numbers

divide-array-in-sets-of-k-consecutive-numbers

划分数组为连续数字的集合

Greedy

Array

Hash Table

Heap (Priority Queue)

给你一个按 非递减顺序 排列的整数数组 <code>nums</code> 。

请你判断是否能在将 <code>nums</code> 分割成 一个或多个子序列 的同时满足下述 两个 条件：

<div class="original__bRMd">
<div>
<ul>
	<li>每个子序列都是一个 连续递增序列（即，每个整数 恰好 比前一个整数大 1 ）。</li>
	<li>所有子序列的长度 至少 为 <code>3</code> 。</li>
</ul>

如果可以分割 <code>nums</code> 并满足上述条件，则返回 <code>true</code> ；否则，返回 <code>false</code> 。
</div>
</div>

&nbsp;

示例 1：

<pre>
输入：nums = [1,2,3,3,4,5]
输出：true
解释：nums 可以分割成以下子序列：
[1,2,3,3,4,5] --&gt; 1, 2, 3
[1,2,3,3,4,5] --&gt; 3, 4, 5
</pre>

示例 2：

<pre>
输入：nums = [1,2,3,3,4,4,5,5]
输出：true
解释：nums 可以分割成以下子序列：
[1,2,3,3,4,4,5,5] --&gt; 1, 2, 3, 4, 5
[1,2,3,3,4,4,5,5] --&gt; 3, 4, 5
</pre>

示例 3：

<pre>
输入：nums = [1,2,3,4,4,5]
输出：false
解释：无法将 nums 分割成长度至少为 3 的连续递增子序列。
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= nums.length &lt;= 104</code></li>
	<li><code>-1000 &lt;= nums[i] &lt;= 1000</code></li>
	<li><code>nums</code> 按非递减顺序排列</li>
</ul>