算法题（求最长连续子序列） _数据结构

本文概述

C++ 14
Java
C++
Java
python
C#

给定整数数组, 请找到最长子序列的长度, 以使子序列中的元素为连续整数, 连续数字可以为任意顺序。
例子:

Input: arr[] = {1, 9, 3, 10, 4, 20, 2} Output: 4 Explanation: The subsequence 1, 3, 4, 2 is the longest subsequence of consecutive elementsInput: arr[] = {36, 41, 56, 35, 44, 33, 34, 92, 43, 32, 42} Output: 5 Explanation: The subsequence 36, 35, 33, 34, 32 is the longest subsequence of consecutive elements.

简单的方法：
这个想法是首先对数组进行排序, 然后找到具有连续元素的最长子数组。
【算法题（求最长连续子序列）】对数组进行排序后, 运行循环并保持计数和最大值(均初始为零)。从头到尾运行一个循环, 如果当前元素不等于前一个元素(元素+1), 则将计数设置为1, 否则增加计数。用最大计数和最大更新最大值。
C++ 14

//C++ program to find longest //contiguous subsequence #include < bits/stdc++.h> using namespace std; //Returns length of the longest //contiguous subsequence int findLongestConseqSubseq( int arr[], int n) { int ans = 0, count = 0; //sort the array sort(arr, arr + n); //find the maximum length //by traversing the array for ( int i = 0; i < n; i++) { //if the current element is equal //to previous element +1 if (i> 0 & & arr[i] == arr[i - 1] + 1) count++; //reset the count else count = 1; //update the maximum ans = max(ans, count); } return ans; } //Driver program int main() { int arr[] = { 1, 9, 3, 10, 4, 20, 2 }; int n = sizeof arr /sizeof arr[0]; cout < < "Length of the Longest contiguous subsequence is " < < findLongestConseqSubseq(arr, n); return 0; }

Java

//Java program to find longest //contiguous subsequence import java.io.*; import java.util.*; class GFG{static int findLongestConseqSubseq( int arr[], int n) {//Sort the array Arrays.sort(arr); int ans = 0 , count = 1 ; //find the maximum length //by traversing the array for ( int i = 1 ; i < n; i++) {//If the current element is //equal to previous element +1 if (arr[i] == arr[i - 1 ] + 1 ) count++; else count = 1 ; //Update the maximum ans = Math.max(ans, count); } return ans; } //Driver code public static void main (String[] args) { int arr[] = { 1 , 9 , 3 , 10 , 4 , 20 , 2 }; int n = arr.length; System.out.println( "Length of the Longest " + "contiguous subsequence is " + findLongestConseqSubseq(arr, n)); } } //This code is contributed by parascoding

输出如下：

Length of the Longest contiguous subsequence is 4

复杂度分析：

时间复杂度：O(nLogn)。
对数组进行排序的时间为O(nlogn)。
辅助空间：O(1)。
由于不需要额外的空间。

感谢Hao.W建议上述解决方案。
高效的解决方案：
这个问题可以在O(n)时间内使用高效的解决方案。这个想法是使用散列。我们首先将所有元素插入组。然后检查连续子序列的所有可能开始。
算法：

创建一个空哈希。
将所有数组元素插入哈希。
对每个元素arr [i]执行以下操作
检查此元素是否是子序列的起点。要检查这一点, 只需在哈希中查找arr [i] – 1(如果未找到), 则这是子序列的第一个元素。
如果此元素是第一个元素, 则从该元素开始计算连续的元素数。从arr [i] + 1进行迭代, 直到找到最后一个元素。
如果计数大于以前找到的最长子序列, 则更新它。

下图是上述方法的模拟：

文章图片
下面是上述方法的实现：
C++

//C++ program to find longest //contiguous subsequence #include < bits/stdc++.h> using namespace std; //Returns length of the longest //contiguous subsequence int findLongestConseqSubseq( int arr[], int n) { unordered_set< int> S; int ans = 0; //Hash all the array elements for ( int i = 0; i < n; i++) S.insert(arr[i]); //check each possible sequence from //the start then update optimal length for ( int i = 0; i < n; i++) { //if current element is the starting //element of a sequence if (S.find(arr[i] - 1) == S.end()) { //Then check for next elements //in the sequence int j = arr[i]; while (S.find(j) != S.end()) j++; //updateoptimal length if //this length is more ans = max(ans, j - arr[i]); } } return ans; } //Driver program int main() { int arr[] = { 1, 9, 3, 10, 4, 20, 2 }; int n = sizeof arr /sizeof arr[0]; cout < < "Length of the Longest contiguous subsequence is " < < findLongestConseqSubseq(arr, n); return 0; }

Java

//Java program to find longest //consecutive subsequence import java.io.*; import java.util.*; class ArrayElements { //Returns length of the longest //consecutive subsequence static int findLongestConseqSubseq( int arr[], int n) { HashSet< Integer> S = new HashSet< Integer> (); int ans = 0 ; //Hash all the array elements for ( int i = 0 ; i < n; ++i) S.add(arr[i]); //check each possible sequence from the start //then update optimal length for ( int i = 0 ; i < n; ++i) { //if current element is the starting //element of a sequence if (!S.contains(arr[i] - 1 )) { //Then check for next elements //in the sequence int j = arr[i]; while (S.contains(j)) j++; //updateoptimal length if this //length is more if (ans < j - arr[i]) ans = j - arr[i]; } } return ans; } //Testing program public static void main(String args[]) { int arr[] = { 1 , 9 , 3 , 10 , 4 , 20 , 2 }; int n = arr.length; System.out.println( "Length of the Longest consecutive subsequence is " + findLongestConseqSubseq(arr, n)); } } //This code is contributed by Aakash Hasija

python

# Python program to find longest contiguous subsequence from sets import Set def findLongestConseqSubseq(arr, n): s = Set () ans = 0 # Hash all the array elements for ele in arr: s.add(ele) # check each possible sequence from the start # then update optimal length for i in range (n): # if current element is the starting # element of a sequence if (arr[i] - 1 ) not in s: # Then check for next elements in the # sequence j = arr[i] while (j in s): j + = 1 # updateoptimal length if this length # is more ans = max (ans, j - arr[i]) return ans # Driver function if __name__ = = '__main__' : n = 7 arr = [ 1 , 9 , 3 , 10 , 4 , 20 , 2 ] print "Length of the Longest contiguous subsequence is " , printfindLongestConseqSubseq(arr, n)# Contributed by: Harshit Sidhwa

using System; using System.Collections.Generic; //C# program to find longest consecutive subsequence public class ArrayElements { //Returns length of the longest consecutive subsequence public static int findLongestConseqSubseq( int [] arr, int n) { HashSet< int> S = new HashSet< int> (); int ans = 0; //Hash all the array elements for ( int i = 0; i < n; ++i) { S.Add(arr[i]); } //check each possible sequence from the start //then update optimal length for ( int i = 0; i < n; ++i) { //if current element is the starting //element of a sequence if (!S.Contains(arr[i] - 1)) { //Then check for next elements in the //sequence int j = arr[i]; while (S.Contains(j)) { j++; } //updateoptimal length if this length //is more if (ans < j - arr[i]) { ans = j - arr[i]; } } } return ans; } //Testing program public static void Main( string [] args) { int [] arr = new int [] { 1, 9, 3, 10, 4, 20, 2 }; int n = arr.Length; Console.WriteLine( "Length of the Longest consecutive subsequence is " + findLongestConseqSubseq(arr, n)); } } //This code is contributed by Shrikant13

输出如下：