具有连续元素的最大子阵列的长度|集2-yiteyi-C++库

给定一个整数数组，找出最长子数组的长度，该子数组包含可以连续排列的数字。在以前的职位，我们讨论了一种假设给定数组中的元素是不同的解决方案。这里我们讨论一种即使输入数组有重复项也能工作的解决方案。例如：

null

Input:  arr[] = {10, 12, 11};Output: Length of the longest contiguous subarray is 3Input:  arr[] = {10, 12, 12, 10, 10, 11, 10};Output: Length of the longest contiguous subarray is 2

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

这个想法与之前的帖子类似。在上一篇文章中，我们检查了最大值减去最小值是否等于结束索引减去开始索引。由于允许重复元素，我们还需要检查子阵列是否包含重复元素。例如，数组{12,14,12}遵循第一个属性，但其中的数字不是连续的元素。为了检查子数组中的重复元素，我们为每个子数组创建一个哈希集，如果在哈希中找到一个元素，则不考虑当前子数组。以下是上述理念的实施。

C++

                         /* CPP program to find length of the largest                       
                         subarray which has all contiguous elements */                       
                         #include<bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // This function prints all distinct elements                       
                         int                                     findLength(                                     int                                     arr[],                                     int                                     n)                       
                         {                       
                                                 int                                     max_len = 1;                                     // Initialize result                       
           
                                                 // One by one fix the starting points                       
                                                 for                                     (                                     int                                     i=0; i<n-1; i++)                       
                                                 {                       
                                                 // Create an empty hash set and                       
                                                 // add i'th element to it.                       
                                                 set<                                     int                                     > myset;                       
                                                 myset.insert(arr[i]);                       
           
                                                 // Initialize max and min in                       
                                                 // current subarray                       
                                                 int                                     mn = arr[i], mx = arr[i];                       
           
                                                 // One by one fix ending points                       
                                                 for                                     (                                     int                                     j=i+1; j<n; j++)                       
                                                 {                       
                                                 // If current element is already                       
                                                 // in hash set, then this subarray                       
                                                 // cannot contain contiguous elements                       
                                                 if                                     (myset.find(arr[j]) != myset.end())                       
                                                 break                                     ;                       
           
                                                 // Else add current element to hash                       
                                                 // set and update min, max if required.                       
                                                 myset.insert(arr[j]);                       
                                                 mn = min(mn, arr[j]);                       
                                                 mx = max(mx, arr[j]);                       
           
                                                 // We have already checked for                       
                                                 // duplicates, now check for other                       
                                                 // property and update max_len                       
                                                 // if needed                       
                                                 if                                     (mx - mn == j - i)                       
                                                 max_len = max(max_len, mx - mn + 1);                       
                                                 }                       
                                                 }                       
                                                 return                                     max_len;                                     // Return result                       
                         }                       
           
                         // Driver method to test above method                       
                         int                                     main ()                       
                         {                       
                                                 int                                     arr[] = {10, 12, 12, 10, 10, 11, 10};                       
                                                 int                                     n =                                     sizeof                                     (arr) /                                     sizeof                                     (arr[0]);                       
                                                 cout <<                                     "Length of the longest contiguous"                       
                                                 <<                                     " subarray is "                                     << findLength(arr, n);                       
                         }                       
           
                         // This article is contributed by Chhavi                       

JAVA

                         /* Java program to find length of the largest subarray which has                       
                                                 all contiguous elements */                       
                         import                                     java.util.*;                       
           
                         class                                     Main                       
                         {                       
                                                 // This function prints all distinct elements                       
                                                 static                                     int                                     findLength(                                     int                                     arr[])                       
                                                 {                       
                                                 int                                     n = arr.length;                       
                                                 int                                     max_len =                                     1                                     ;                                     // Initialize result                       
           
                                                 // One by one fix the starting points                       
                                                 for                                     (                                     int                                     i=                                     0                                     ; i<n-                                     1                                     ; i++)                       
                                                 {                       
                                                 // Create an empty hash set and add i'th element                       
                                                 // to it.                       
                                                 HashSet<Integer> set =                                     new                                     HashSet<>();                       
                                                 set.add(arr[i]);                       
           
                                                 // Initialize max and min in current subarray                       
                                                 int                                     mn = arr[i], mx = arr[i];                       
           
                                                 // One by one fix ending points                       
                                                 for                                     (                                     int                                     j=i+                                     1                                     ; j<n; j++)                       
                                                 {                       
                                                 // If current element is already in hash set, then                       
                                                 // this subarray cannot contain contiguous elements                       
                                                 if                                     (set.contains(arr[j]))                       
                                                 break                                     ;                       
           
                                                 // Else add current element to hash set and update                       
                                                 // min, max if required.                       
                                                 set.add(arr[j]);                       
                                                 mn = Math.min(mn, arr[j]);                       
                                                 mx = Math.max(mx, arr[j]);                       
           
                                                 // We have already checked for duplicates, now check                       
                                                 // for other property and update max_len if needed                       
                                                 if                                     (mx-mn == j-i)                       
                                                 max_len = Math.max(max_len, mx-mn+                                     1                                     );                       
                                                 }                       
                                                 }                       
                                                 return                                     max_len;                                     // Return result                       
                                                 }                       
           
                                                 // Driver method to test above method                       
                                                 public                                     static                                     void                                     main (String[] args)                       
                                                 {                       
                                                 int                                     arr[] =  {                                     10                                     ,                                     12                                     ,                                     12                                     ,                                     10                                     ,                                     10                                     ,                                     11                                     ,                                     10                                     };                       
                                                 System.out.println(                                     "Length of the longest contiguous subarray is "                                     +                       
                                                 findLength(arr));                       
                                                 }                       
                         }                       

Python3

                         # python program to find length of the largest                       
                         # subarray which has all contiguous elements */                       
           
                         # This function prints all distinct elements                       
                         def                                     findLenght(arr, n):                       
                                                 max_len                                     =                                     1                       
                                                 for                                     i                                     in                                     range                                     (                                     0                                     ,n                                     -                                     1                                     ):                       
           
                                                 # Create an empty hash set and                       
                                                 # add i'th element to it                       
                                                 myset                                     =                                     set                                     ()                       
                                                 myset.add(arr[i])                       
           
                                                 # Initialize max and min in                       
                                                 # current subarray                       
                                                 mn                                     =                                     arr[i]                       
                                                 mx                                     =                                     arr[i]                       
                                                 for                                     j                                     in                                     range                                     (i                                     +                                     1                                     ,n):                       
           
                                                 # If current element is already                       
                                                 # in hash set, then this subarray                       
                                                 # cannot contain contiguous elements                       
                                                 if                                     arr[j]                                     in                                     myset:                       
                                                 break                       
           
           
                                                 # Else add current element to hash                       
                                                 # set and update min, max if required.                       
                                                 myset.add(arr[j])                       
                                                 mn                                     =                                     min                                     (mn, arr[j])                       
                                                 mx                                     =                                     max                                     (mx, arr[j])                       
           
                                                 # We have already checked for                       
                                                 # duplicates, now check for other                       
                                                 #property and update max_len                       
                                                 # if needed                       
                                                 if                                     mx                                     -                                     mn                                     =                                     =                                     j                                     -                                     i:                       
                                                 max_len                                     =                                     max                                     (max_len, mx                                     -                                     mn                                     +                                     1                                     )                       
           
                                                 return                                     max_len                                     # Return result                       
           
           
                         # Driver code                       
           
                         arr                                     =                                     [                                     10                                     ,                                     12                                     ,                                     12                                     ,                                     10                                     ,                                     10                                     ,                                     11                                     ,                                     10                                     ]                       
                         n                                     =                                     len                                     (arr)                       
                         print                                     (                                     "Length of the longest contiguous subarray is"                                     ,                       
                                                 findLenght(arr,n))                       
           
                         # This code is contributed by Shrikant13                       

C#

                         /* C# program to find length of the largest                       
                         subarray which has all contiguous elements */                       
                         using                                     System;                       
                         using                                     System.Collections.Generic;                       
           
                         class                                     GFG {                       
                                   
                                                 // This function prints all distinct                       
                                                 // elements                       
                                                 static                                     int                                     findLength(                                     int                                     []arr)                       
                                                 {                       
                                                 int                                     n = arr.Length;                       
                                                 int                                     max_len = 1;                                     // Initialize result                       
           
                                                 // One by one fix the starting points                       
                                                 for                                     (                                     int                                     i = 0; i < n-1; i++)                       
                                                 {                       
                                   
                                                 // Create an empty hash set and                       
                                                 // add i'th element to it.                       
                                                 HashSet<                                     int                                     >                                     set                                     =                                     new                                     HashSet<                                     int                                     >();                       
                                                 set                                     .Add(arr[i]);                       
           
                                                 // Initialize max and min in current                       
                                                 // subarray                       
                                                 int                                     mn = arr[i], mx = arr[i];                       
           
                                                 // One by one fix ending points                       
                                                 for                                     (                                     int                                     j = i+1; j < n; j++)                       
                                                 {                       
                                   
                                                 // If current element is already                       
                                                 // in hash set, then this subarray                       
                                                 // cannot contain contiguous                       
                                                 // elements                       
                                                 if                                     (                                     set                                     .Contains(arr[j]))                       
                                                 break                                     ;                       
           
                                                 // Else add current element to                       
                                                 // hash set and update min,                       
                                                 // max if required.                       
                                                 set                                     .Add(arr[j]);                       
                                                 mn = Math.Min(mn, arr[j]);                       
                                                 mx = Math.Max(mx, arr[j]);                       
           
                                                 // We have already checked for                       
                                                 // duplicates, now check for                       
                                                 // other property and update                       
                                                 // max_len if needed                       
                                                 if                                     (mx-mn == j-i)                       
                                                 max_len = Math.Max(max_len,                       
                                                 mx - mn + 1);                       
                                                 }                       
                                                 }                       
                                   
                                                 return                                     max_len;                                     // Return result                       
                                                 }                       
                                   
                                                 // Driver function                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 int                                     []arr = {10, 12, 12, 10, 10, 11, 10};                       
                                                 Console.WriteLine(                                     "Length of the longest"                       
                                                 +                                     " contiguous subarray is "                                     +                       
                                                 findLength(arr));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Sam007                       

Javascript

                         <script>                       
                         /* javascript program to find length of the largest subarray which has                       
                                                 all contiguous elements */                       
                                                 // This function prints all distinct elements                       
                                                 function                                     findLength(arr) {                       
                                                 var                                     n = arr.length;                       
                                                 var                                     max_len = 1;                                     // Initialize result                       
           
                                                 // One by one fix the starting points                       
                                                 for                                     (i = 0; i < n - 1; i++) {                       
                                                 // Create an empty hash set and add i'th element                       
                                                 // to it.                       
                                                 var                                     set =                                     new                                     Set();                       
                                                 set.add(arr[i]);                       
           
                                                 // Initialize max and min in current subarray                       
                                                 var                                     mn = arr[i], mx = arr[i];                       
           
                                                 // One by one fix ending points                       
                                                 for                                     (j = i + 1; j < n; j++) {                       
                                                 // If current element is already in hash set, then                       
                                                 // this subarray cannot contain contiguous elements                       
                                                 if                                     (set.has(arr[j]))                       
                                                 break                                     ;                       
           
                                                 // Else add current element to hash set and update                       
                                                 // min, max if required.                       
                                                 set.add(arr[j]);                       
                                                 mn = Math.min(mn, arr[j]);                       
                                                 mx = Math.max(mx, arr[j]);                       
           
                                                 // We have already checked for duplicates, now check                       
                                                 // for other property and update max_len if needed                       
                                                 if                                     (mx - mn == j - i)                       
                                                 max_len = Math.max(max_len, mx - mn + 1);                       
                                                 }                       
                                                 }                       
                                                 return                                     max_len;                                     // Return result                       
                                                 }                       
           
                                                 // Driver method to test above method                       
                                   
                                                 var                                     arr = [ 10, 12, 12, 10, 10, 11, 10 ];                       
                                                 document.write(                                     "Length of the longest contiguous subarray is "                       
                                                 + findLength(arr));                       
           
                         // This code contributed by gauravrajput1                       
                         </script>                       

输出：

Length of the longest contiguous subarray is 2

上述解的时间复杂度为O（n） ^2. )假设像add（）和contains（）这样的散列集操作在O（1）时间内工作。本文由阿琼。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章