最长的子数组，任意两个不同值之间的差值恰好为K

2021年4月19日12:18:48 发表评论 694 次浏览

本文概述

给定一个长度为N且整数为K的数组arr[]，任务是找到任意两个不同值之间的差值为K的最长子数组。打印得到的最长子数组的长度。否则，如果没有这样的子数组，则打印-1。

例子：

输入：arr[] = {0, 0, 1, 1, 3, 3, 3}, K = 1
输出：4
说明：
子数组{0, 0, 1, 1}是仅有的两个子数组之间有差异的子数组等于K(= 1)的不同值。因此, 长度等于4。
输入：arr[] = {5, 7, 1, 1, 2, 2, 4, 4, 4, 5, 5, 4, 5, 8, 9}, K = 1
输出：7说明：
子数组{1、1、2}, {4、4、4、5、5、4、5}和{8、9}是仅有的两个等于K(= 1)的不同值之间具有差异的子数组。其中最长的子数组是{4, 4, 4, 5, 5, 4, 5}。因此, 长度为7。

简单的方法：

  • 一个简单的解决方案是一一考虑所有子数组, 然后查找仅包含两个不同值的子数组, 这两个值之间的差为K。不断更新获得的子数组的最大长度。
  • 最后打印获得的最大长度。

时间复杂度：O(N^3)

辅助空间：O(N)

高效方法：

可以观察到，对于任意两个元素之差为K的元素所组成的子数组，该子数组必须只有两个不同的值。因此，可以进一步优化上述方法，使用set寻找只有两个不同值且差k的最长子数组，按照以下步骤解决问题:

  • 从数组的起始索引开始第一个子数组。
  • 将该元素插入集合。继续下一个元素, 并检查该元素是否与前一个元素相同或绝对差为K。
  • 如果是这样, 则将该元素插入集合, 然后继续增加子数组的长度。一旦找到第三个不同的元素, 请将当前子数组的长度与子数组的最大长度进行比较, 然后进行相应更新。
  • 将获得的新元素更新到集合中, 然后重复上述步骤。
  • 遍历整个数组后, 打印获得的最大长度。

下面是上述方法的实现：

C ++

//C++ implementation to find the
//longest subarray consisting of
//only two values with difference K
#include <bits/stdc++.h>
using namespace std;
 
//Function to return the length
//of the longest sub-array
int longestSubarray( int arr[], int n, int k)
{
     int i, j, Max = 1;
 
     //Initialize set
     set<int> s;
 
     for (i = 0; i <n - 1; i++) {
         //Store 1st element of
         //sub-array into set
         s.insert(arr[i]);
 
         for (j = i + 1; j <n; j++) {
             //Check absolute difference
             //between two elements
 
             if ( abs (arr[i] - arr[j]) == 0
                 || abs (arr[i] - arr[j]) == k) {
 
                 //If the new element is not
                 //present in the set
                 if (!s.count(arr[j])) {
 
                     //If the set contains
                     //two elements
                     if (s.size() == 2)
                         break ;
 
                     //Otherwise
                     else
                         s.insert(arr[j]);
                 }
             }
             else
                 break ;
         }
 
         if (s.size() == 2) {
 
             //Update the maximum
             //length
             Max = max(Max, j - i);
 
             //Remove the set
             //elements
             s.clear();
         }
         else
             s.clear();
     }
 
     return Max;
}
 
//Driver Code
int main()
{
     int arr[] = { 1, 0, 2, 2, 5, 5, 5 };
 
     int N = sizeof (arr)
             /sizeof (arr[0]);
     int K = 1;
 
     int length = longestSubarray(
         arr, N, K);
 
     if (length == 1)
         cout <<-1;
     else
         cout <<length;
 
     return 0;
}

Java

//Java implementation to find the
//longest subarray consisting of
//only two values with difference K
import java.util.*;
 
class GFG{
 
//Function to return the length
//of the longest sub-array
static int longestSubarray( int arr[], int n, int k)
{
     int i, j, Max = 1 ;
 
     //Initialize set
     HashSet<Integer> s = new HashSet<Integer>();
 
     for (i = 0 ; i <n - 1 ; i++)
     {
         
         //Store 1st element of
         //sub-array into set
         s.add(arr[i]);
 
         for (j = i + 1 ; j <n; j++)
         {
             
             //Check absolute difference
             //between two elements
             if (Math.abs(arr[i] - arr[j]) == 0 ||
                 Math.abs(arr[i] - arr[j]) == k)
             {
                 
                 //If the new element is not
                 //present in the set
                 if (!s.contains(arr[j]))
                 {
                     
                     //If the set contains
                     //two elements
                     if (s.size() == 2 )
                         break ;
 
                     //Otherwise
                     else
                         s.add(arr[j]);
                 }
             }
             else
                 break ;
         }
         if (s.size() == 2 )
         {
             
             //Update the maximum
             //length
             Max = Math.max(Max, j - i);
 
             //Remove the set
             //elements
             s.clear();
         }
         else
             s.clear();
     }
     return Max;
}
 
//Driver Code
public static void main(String[] args)
{
     int arr[] = { 1 , 0 , 2 , 2 , 5 , 5 , 5 };
 
     int N = arr.length;
     int K = 1 ;
     int length = longestSubarray(arr, N, K);
 
     if (length == 1 )
         System.out.print(- 1 );
     else
         System.out.print(length);
}
}
 
//This code is contributed by Princi Singh

Python3

# Python3 implementation to find the 
# longest subarray consisting of 
# only two values  with difference K
 
# Function to return the length 
# of the longest sub-array
def longestSubarray (arr, n, k):
 
     Max = 1
 
     # Initialize set
     s = set ()
 
     for i in range (n - 1 ):
 
         # Store 1st element of
         # sub-array into set
         s.add(arr[i])
 
         for j in range (i + 1 , n):
             
             # Check absolute difference
             # between two elements
             if ( abs (arr[i] - arr[j]) = = 0 or
                 abs (arr[i] - arr[j]) = = k):
 
                 # If the new element is not
                 # present in the set
                 if ( not arr[j] in s):
 
                     # If the set contains
                     # two elements
                     if ( len (s) = = 2 ):
                         break
 
                     # Otherwise
                     else :
                         s.add(arr[j])
                         
             else :
                 break
 
         if ( len (s) = = 2 ):
 
             # Update the maximum length
             Max = max ( Max , j - i)
 
             # Remove the set elements
             s.clear()
 
         else :
             s.clear()
 
     return Max
 
# Driver Code
if __name__ = = '__main__' :
     
     arr = [ 1 , 0 , 2 , 2 , 5 , 5 , 5 ]
 
     N = len (arr)
     K = 1
 
     length = longestSubarray(arr, N, K)
 
     if (length = = 1 ):
         print ( "-1" )
     else :
         print (length)
 
# This code is contributed by himanshu77

C#

//C# implementation to find the
//longest subarray consisting of
//only two values with difference K
using System;
using System.Collections.Generic;
 
class GFG{
 
//Function to return the length
//of the longest sub-array
static int longestSubarray( int []arr, int n, int k)
{
     int i, j, Max = 1;
 
     //Initialize set
     HashSet<int> s = new HashSet<int>();
 
     for (i = 0; i <n - 1; i++)
     {
         
         //Store 1st element of
         //sub-array into set
         s.Add(arr[i]);
 
         for (j = i + 1; j <n; j++)
         {
             
             //Check absolute difference
             //between two elements
             if (Math.Abs(arr[i] - arr[j]) == 0 ||
                 Math.Abs(arr[i] - arr[j]) == k)
             {
                 
                 //If the new element is not
                 //present in the set
                 if (!s.Contains(arr[j]))
                 {
                     
                     //If the set contains
                     //two elements
                     if (s.Count == 2)
                         break ;
 
                     //Otherwise
                     else
                         s.Add(arr[j]);
                 }
             }
             else
                 break ;
         }
         if (s.Count == 2)
         {
             
             //Update the maximum
             //length
             Max = Math.Max(Max, j - i);
 
             //Remove the set
             //elements
             s.Clear();
         }
         else
             s.Clear();
     }
     return Max;
}
 
//Driver Code
public static void Main(String[] args)
{
     int []arr = { 1, 0, 2, 2, 5, 5, 5 };
 
     int N = arr.Length;
     int K = 1;
     int length = longestSubarray(arr, N, K);
 
     if (length == 1)
         Console.Write(-1);
     else
         Console.Write(length);
}
}
 
//This code is contributed by Princi Singh

输出如下：

2

时间复杂度：O(N^2 * logN)

辅助空间：O(N)

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: