不超过K个不同元素的最长子阵列-yiteyi-C++库

给定N个元素和一个数字K，找到不超过K个不同元素的最长子阵列。（可以少于K） 例如：

null

Input : arr[] = {1, 2, 3, 4, 5}            k = 6 Output : 1 2 3 4 5 Explanation: The whole array has only 5 distinct elements which is less than k, so we print the array itself.Input: arr[] = {6, 5, 1, 2, 3, 2, 1, 4, 5}           k = 3Output: 1 2 3 2 1, The output is the longest subarray with 3distinct elements.

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

A. 幼稚的方法 将在数组中遍历，并对每个子数组使用哈希，并检查不超过K个不同元素的最长子数组。一 有效的方法 就是使用两点我们维护一个散列来计算元素的出现次数。我们从一开始就对不同的元素进行计数，直到数量超过k。一旦超过k，我们就开始从子数组开始的地方开始减少散列中元素的计数，并随着子数组的减少而减少长度，这样指针就会向右移动。我们不断移除元素，直到我们再次得到k个不同的元素。我们继续这个过程，直到我们再次有超过k个不同的元素，并保持左指针不变，直到那时。如果新的子数组长度大于前一个子数组长度，我们将根据该长度更新开始和结束。

C++

                         // CPP program to find longest subarray with                       
                         // k or less distinct elements.                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // function to print the longest sub-array                       
                         void                                     longest(                                     int                                     a[],                                     int                                     n,                                     int                                     k)                       
                         {                       
                                                 unordered_map<                                     int                                     ,                                     int                                     > freq;                       
           
                                                 int                                     start = 0, end = 0, now = 0, l = 0;                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++) {                       
           
                                                 // mark the element visited                       
                                                 freq[a[i]]++;                       
           
                                                 // if its visited first time, then increase                       
                                                 // the counter of distinct elements by 1                       
                                                 if                                     (freq[a[i]] == 1)                       
                                                 now++;                       
           
                                                 // When the counter of distinct elements                       
                                                 // increases from k, then reduce it to k                       
                                                 while                                     (now > k) {                       
           
                                                 // from the left, reduce the number of                       
                                                 // time of visit                       
                                                 freq[a[l]]--;                       
           
                                                 // if the reduced visited time element                       
                                                 // is not present in further segment                       
                                                 // then decrease the count of distinct                       
                                                 // elements                       
                                                 if                                     (freq[a[l]] == 0)                       
                                                 now--;                       
           
                                                 // increase the subsegment mark                       
                                                 l++;                       
                                                 }                       
           
                                                 // check length of longest sub-segment                       
                                                 // when greater then previous best                       
                                                 // then change it                       
                                                 if                                     (i - l + 1 >= end - start + 1)                       
                                                 end = i, start = l;                       
                                                 }                       
           
                                                 // print the longest sub-segment                       
                                                 for                                     (                                     int                                     i = start; i <= end; i++)                       
                                                 cout << a[i] <<                                     " "                                     ;                       
                         }                       
           
                         // driver program to test the above function                       
                         int                                     main()                       
                         {                       
                                                 int                                     a[] = { 6, 5, 1, 2, 3, 2, 1, 4, 5 };                       
                                                 int                                     n =                                     sizeof                                     (a) /                                     sizeof                                     (a[0]);                       
                                                 int                                     k = 3;                       
                                                 longest(a, n, k);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to find longest subarray with                       
                         // k or less distinct elements.                       
                         import                                     java.util.*;                       
           
                         class                                     GFG                       
                         {                       
           
                         // function to print the longest sub-array                       
                         static                                     void                                     longest(                                     int                                     a[],                                     int                                     n,                                     int                                     k)                       
                         {                       
                                                 int                                     [] freq =                                     new                                     int                                     [                                     7                                     ];                       
           
                                                 int                                     start =                                     0                                     , end =                                     0                                     , now =                                     0                                     , l =                                     0                                     ;                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; i++)                       
                                                 {                       
           
                                                 // mark the element visited                       
                                                 freq[a[i]]++;                       
           
                                                 // if its visited first time, then increase                       
                                                 // the counter of distinct elements by 1                       
                                                 if                                     (freq[a[i]] ==                                     1                                     )                       
                                                 now++;                       
           
                                                 // When the counter of distinct elements                       
                                                 // increases from k, then reduce it to k                       
                                                 while                                     (now > k)                       
                                                 {                       
           
                                                 // from the left, reduce the number of                       
                                                 // time of visit                       
                                                 freq[a[l]]--;                       
           
                                                 // if the reduced visited time element                       
                                                 // is not present in further segment                       
                                                 // then decrease the count of distinct                       
                                                 // elements                       
                                                 if                                     (freq[a[l]] ==                                     0                                     )                       
                                                 now--;                       
           
                                                 // increase the subsegment mark                       
                                                 l++;                       
                                                 }                       
           
                                                 // check length of longest sub-segment                       
                                                 // when greater then previous best                       
                                                 // then change it                       
                                                 if                                     (i - l +                                     1                                     >= end - start +                                     1                                     )                       
                                                 {                       
                                                 end = i;                       
                                                 start = l;                       
                                                 }                       
                                                 }                       
           
                                                 // print the longest sub-segment                       
                                                 for                                     (                                     int                                     i = start; i <= end; i++)                       
                                                 System.out.print(a[i]+                                     " "                                     );                       
                         }                       
           
                         // Driver code                       
                         public                                     static                                     void                                     main(String args[])                       
                         {                       
                                                 int                                     a[] = {                                     6                                     ,                                     5                                     ,                                     1                                     ,                                     2                                     ,                                     3                                     ,                                     2                                     ,                                     1                                     ,                                     4                                     ,                                     5                                     };                       
                                                 int                                     n = a.length;                       
                                                 int                                     k =                                     3                                     ;                       
                                                 longest(a, n, k);                       
                         }                       
                         }                       
           
                         // This code is contributed by                       
                         // Surendra_Gangwar                       

Python 3

                         # Python 3 program to find longest                       
                         # subarray with k or less distinct elements.                       
           
                         # function to print the longest sub-array                       
                         import                                     collections                       
                         def                                     longest(a, n, k):                       
           
                                                 freq                                     =                                     collections.defaultdict(                                     int                                     )                       
           
                                                 start                                     =                                     0                       
                                                 end                                     =                                     0                       
                                                 now                                     =                                     0                       
                                                 l                                     =                                     0                       
                                                 for                                     i                                     in                                     range                                     (n):                       
           
                                                 # mark the element visited                       
                                                 freq[a[i]]                                     +                                     =                                     1                       
           
                                                 # if its visited first time, then increase                       
                                                 # the counter of distinct elements by 1                       
                                                 if                                     (freq[a[i]]                                     =                                     =                                     1                                     ):                       
                                                 now                                     +                                     =                                     1                       
           
                                                 # When the counter of distinct elements                       
                                                 # increases from k, then reduce it to k                       
                                                 while                                     (now > k) :                       
           
                                                 # from the left, reduce the number                       
                                                 # of time of visit                       
                                                 freq[a[l]]                                     -                                     =                                     1                       
           
                                                 # if the reduced visited time element                       
                                                 # is not present in further segment                       
                                                 # then decrease the count of distinct                       
                                                 # elements                       
                                                 if                                     (freq[a[l]]                                     =                                     =                                     0                                     ):                       
                                                 now                                     -                                     =                                     1                       
           
                                                 # increase the subsegment mark                       
                                                 l                                     +                                     =                                     1                       
           
                                                 # check length of longest sub-segment                       
                                                 # when greater then previous best                       
                                                 # then change it                       
                                                 if                                     (i                                     -                                     l                                     +                                     1                                     >                                     =                                     end                                     -                                     start                                     +                                     1                                     ):                       
                                                 end                                     =                                     i                       
                                                 start                                     =                                     l                       
           
                                                 # print the longest sub-segment                       
                                                 for                                     i                                     in                                     range                                     (start, end                                     +                                     1                                     ):                       
                                                 print                                     (a[i], end                                     =                                     " "                                     )                       
           
                         # Driver Code                       
                         if                                     __name__                                     =                                     =                                     "__main__"                                     :                       
           
                                                 a                                     =                                     [                                     6                                     ,                                     5                                     ,                                     1                                     ,                                     2                                     ,                                     3                                     ,                       
                                                 2                                     ,                                     1                                     ,                                     4                                     ,                                     5                                     ]                       
                                                 n                                     =                                     len                                     (a)                       
                                                 k                                     =                                     3                       
                                                 longest(a, n, k)                       
           
                         # This code is contributed                       
                         # by ChitraNayal                       

C#

                         // C# program to find longest subarray with                       
                         // k or less distinct elements.                       
                         using                                     System;                       
                                   
                         class                                     GFG                       
                         {                       
           
                         // function to print the longest sub-array                       
                         static                                     void                                     longest(                                     int                                     []a,                                     int                                     n,                                     int                                     k)                       
                         {                       
                                                 int                                     [] freq =                                     new                                     int                                     [7];                       
           
                                                 int                                     start = 0, end = 0, now = 0, l = 0;                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 {                       
           
                                                 // mark the element visited                       
                                                 freq[a[i]]++;                       
           
                                                 // if its visited first time, then increase                       
                                                 // the counter of distinct elements by 1                       
                                                 if                                     (freq[a[i]] == 1)                       
                                                 now++;                       
           
                                                 // When the counter of distinct elements                       
                                                 // increases from k, then reduce it to k                       
                                                 while                                     (now > k)                       
                                                 {                       
           
                                                 // from the left, reduce the number of                       
                                                 // time of visit                       
                                                 freq[a[l]]--;                       
           
                                                 // if the reduced visited time element                       
                                                 // is not present in further segment                       
                                                 // then decrease the count of distinct                       
                                                 // elements                       
                                                 if                                     (freq[a[l]] == 0)                       
                                                 now--;                       
           
                                                 // increase the subsegment mark                       
                                                 l++;                       
                                                 }                       
           
                                                 // check length of longest sub-segment                       
                                                 // when greater then previous best                       
                                                 // then change it                       
                                                 if                                     (i - l + 1 >= end - start + 1)                       
                                                 {                       
                                                 end = i;                       
                                                 start = l;                       
                                                 }                       
                                                 }                       
           
                                                 // print the longest sub-segment                       
                                                 for                                     (                                     int                                     i = start; i <= end; i++)                       
                                                 Console.Write(a[i]+                                     " "                                     );                       
                         }                       
           
                         // Driver code                       
                         public                                     static                                     void                                     Main(String []args)                       
                         {                       
                                                 int                                     []a = { 6, 5, 1, 2, 3, 2, 1, 4, 5 };                       
                                                 int                                     n = a.Length;                       
                                                 int                                     k = 3;                       
                                                 longest(a, n, k);                       
                         }                       
                         }                       
           
                         // This code contributed by Rajput-Ji                       

Javascript

                         <script>                       
           
                         // JavaScript program to find longest subarray with                       
                         // k or less distinct elements.                       
           
                         // function to print the longest sub-array                       
                         function                                     longest(a, n, k)                       
                         {                       
                                                 var                                     freq = Array(7).fill(0);                       
           
                                                 var                                     start = 0, end = 0, now = 0, l = 0;                       
                                                 for                                     (                                     var                                     i = 0; i < n; i++)                       
                                                 {                       
           
                                                 // mark the element visited                       
                                                 freq[a[i]]++;                       
           
                                                 // if its visited first time, then increase                       
                                                 // the counter of distinct elements by 1                       
                                                 if                                     (freq[a[i]] == 1)                       
                                                 now++;                       
           
                                                 // When the counter of distinct elements                       
                                                 // increases from k, then reduce it to k                       
                                                 while                                     (now > k)                       
                                                 {                       
           
                                                 // from the left, reduce the number of                       
                                                 // time of visit                       
                                                 freq[a[l]]--;                       
           
                                                 // if the reduced visited time element                       
                                                 // is not present in further segment                       
                                                 // then decrease the count of distinct                       
                                                 // elements                       
                                                 if                                     (freq[a[l]] == 0)                       
                                                 now--;                       
           
                                                 // increase the subsegment mark                       
                                                 l++;                       
                                                 }                       
           
                                                 // check length of longest sub-segment                       
                                                 // when greater then previous best                       
                                                 // then change it                       
                                                 if                                     (i - l + 1 >= end - start + 1)                       
                                                 {                       
                                                 end = i;                       
                                                 start = l;                       
                                                 }                       
                                                 }                       
           
                                                 // print the longest sub-segment                       
                                                 for                                     (                                     var                                     i = start; i <= end; i++)                       
                                                 document.write(a[i]+                                     " "                                     );                       
                         }                       
           
                         // driver program to test the above function                       
                         var                                     a = [6, 5, 1, 2, 3, 2, 1, 4, 5];                       
                         var                                     n = a.length;                       
                         var                                     k = 3;                       
                         longest(a, n, k);                       
           
                         </script>                       

输出：

1 2 3 2 1

时间复杂性： O（n）本文由 奋斗者 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用贡献极客。组织或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

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

THE END

技术文章