Java 中的最长连续子序列

给定一个整数数组。我们的任务是找出输入数组中连续整数子序列的最长长度。在输入数组中，连续整数可能在一起也可能不在一起。

示例：1

输入

int arr[] = {11, 39, 13, 10, 14, 20, 12, 15}

输出 6

解释： 由元素 11, 13, 10, 14, 12 和 15 组成的子序列是长度为 6 的最长连续整数子序列。因此，输出为 6。

示例：2

输入

int arr[] = {136, 141, 156, 135, 144, 133, 134, 192, 143, 132, 142}

输出 6

解释： 由元素 136, 135, 133, 134 和 132 组成的子序列是长度为 5 的最长连续整数子序列。因此，输出为 5。

方法：使用排序

我们可以使用排序技术，通过该技术，连续的元素将聚集在一起。之后，我们可以运行一个循环来识别最长的连续元素。观察以下步骤。

步骤 1： 声明两个变量 answer 和 cntConsecutive，并将这两个变量的值都设为 0。

步骤 2： 对输入数组 inputArr[] 进行排序。

步骤 3： 通过遍历输入数组 inputArr[]，将唯一元素保留在 distArr[] 数组（或 ArrayList）中。

步骤 4： 现在，遍历 distArr[] 数组以计算连续元素的数量。当找到前一个或下一个连续元素时，持续更新 cntConsecutive 变量。同时，持续更新 answer 变量。

步骤 5： 返回 answer。

观察上述步骤的实现。

文件名： LongestConsecutiveSubsequence.java

输出

For the input array: 
11 39 13 10 14 20 12 15 
The length of the longest consecutive subsequence is: 6


For the input array: 
136 141 156 135 144 133 134 192 143 132 142 
The length of the longest consecutive subsequence is: 5

复杂度分析： 由于排序，程序的 time complexity 为 O(N * log(N))。程序的 space complexity 为 O(N)，其中 N 是输入数组中存在的元素总数。space complexity 为 O(N) 是因为程序使用了 ArrayList 来存储输入数组的唯一元素。

方法：使用优先队列

也可以使用优先队列来找到所需的结果。观察以下步骤。

步骤 1： 创建一个用于存储元素的优先队列。使用循环将所有元素推送到优先队列中。同时，创建一个 answer 变量并将其值设为 0。

步骤 2： 将优先队列的第一个元素存储在名为 count 的变量中。

步骤 3： 从优先队列中移除该元素。

步骤 4： 计算新 peek 元素与移除的第一个元素之间的差值。

步骤 5： 如果差值为 1，则将 count 加 1，然后重复步骤 2 和步骤 3。

步骤 6： 如果差值大于 1，则将 count 设为 1，然后重复步骤 2 和步骤 3。

步骤 7： 如果差值为 0，则重复步骤 2 和步骤 3。

步骤 8： 将 count 变量的值与 answer 变量进行比较，如果 count 的值大于 answer，则将 count 的值赋给 answer 变量。

步骤 9： 直到优先队列为空，重复步骤 2 到 8。

步骤 10： 返回 answer 变量的值。

让我们看看上述步骤的实现。

文件名： LongestConsecutiveSubsequence1.java

输出

For the input array: 
11 39 13 10 14 20 12 15 
The length of the longest consecutive subsequence is: 6


For the input array: 
136 141 156 135 144 133 134 192 143 132 142 
The length of the longest consecutive subsequence is: 5

复杂度分析： 程序的 time complexity 和 space complexity 与上一个程序相同。

方法：使用 HashSet

我们知道哈希集永远不会包含重复元素。因此，我们将所有元素放入哈希集中，哈希集会简单地丢弃重复值。因此，哈希集中只剩下唯一元素。现在，我们要做的就是找到连续子序列的第一个元素，然后借助哈希集。请看以下步骤。

步骤 1： 创建一个包含整数的哈希集实例。同时，创建一个 answer 变量并将其值设为零。

步骤 2： 将输入数组的所有元素插入哈希集中。

步骤 3： 对于每个元素 inputArr[i]，执行以下操作：

• 检查元素 inputArr[i] 是否存在于哈希集中。
• 如果存在，则检查子序列的开头。我们可以通过检查 inputArr[i] - 1 是否存在来做到这一点。如果不存在，则 inputArr[i] 是子序列的开头。如果存在，则查找另一个元素。
• 找到第一个元素后，使用循环检查 inputArr[i] + 1 是否存在。如果存在，则创建一个初始值为零的变量并将其计数加 1。循环结束后，将其值与 answer 进行比较，如果值更大，则将其赋给 answer。此外，从哈希集中删除循环遍历过的所有元素。

步骤 4： 返回 answer 变量的值。

观察上述步骤的实现。

文件名： LongestConsecutiveSubsequence1.java

输出

For the input array: 
11 39 13 10 14 20 12 15 
The length of the longest consecutive subsequence is: 6


For the input array: 
136 141 156 135 144 133 134 192 143 132 142 
The length of the longest consecutive subsequence is: 5

复杂度分析： 在上述程序中，一个元素最多可以被遍历三次。因此，程序的 time complexity 为 O(3 * n)，渐进地写为 O(n)，其中 n 是输入数组中存在的元素总数。程序的 space complexity 与上一个程序相同。