具有连续元素的最大子数组的长度  


难度级别 中等
经常问 土砖 亚马逊 彭博 思科 克拉 单排解决方案 Paytm PayU 阳狮精明 SAP实验室
排列 哈希

问题“具有连续元素的最大子数组的长度”指出给您一个 整数 排列。 问题陈述要求找出最长的连续子数组的长度,该数组的元素可以按顺序排列(连续,升序或降序)。 数组中的数字可以多次出现。

使用案列  

具有连续元素的最大子数组的长度

arr[] = {10, 12, 13, 11, 8, 10, 11, 10}
4

说明

从第0个索引到第3个索引的数字包含数字10、12、13、11,可以以长度为10的11、12、13、4的方式排列。

arr[] = {1, 1, 3, 2, 8, 4, 8, 10}
3

说明

从第一个索引到第三个索引的数字包含数字1、3、1,它们可以以长度为3的方式2、1、2进行排列。

算法  

  1. 最长长度 到1。
  2. 打开一个循环,i = 0,而我<l -1,
    1. 声明一个 并将arr [i]添加到集合中。
    2. 设定值 麦克斯伦 以及 民伦 到arr [i]。
    3. 打开一个循环,从j = i + 1开始,而j <l,
      1. 检查Set是否具有arr [j]的值,
        1. 如果为真,则中断。
        2. 别的,
          1. 将arr [j]添加到Set中。
          2. 找出minlen和arr [j]之间的最小值并将其存储到minlen。
          3. 找出maxlen和arr [j]之间的最大值,并将其存储到maxlen。
          4. 检查maxlen-min = = j – i
            1. 如果为true,则找出maxLength和max-minlen +1之间的最大值,并将其存储到maxLength。
  3. 返回maxLength。
参见
从四个排序数组中计算四倍,其总和等于给定值x

说明

给我们一个问题,要求找出最长的连续子数组的长度,该数组具有可以按顺序排列的一些数字。 给定的数组可能存在重复的数字。 我们也需要处理这种情况。 为了获得解决方案,我们将使用 还有一个嵌套循环,它将处理重复的元素。

让我们考虑一个例子:

使用案列

Arr [] = {10、12、13、11、8、10}

打开循环后,我们将使用Set并一次添加一个数字,并将maxlen和minlen的值设置为arr [i]。 然后打开一个嵌套循环,该循环从当前元素之前的一个元素开始,因为我们已经将当前元素插入到Set中。 检查Set是否包含arr [j]的值,如果找到元素,则中断。 否则将arr [j]的值插入Set中,找出maxlen和arr [j]之间的最大值,以及minlen和arr [j]之间的最小值,并将其分别存储到maxlen和minlen。 检查maxlen-min是否等于ji,然后更新maxLength的值。

maxLength = 1。

i = 0,mySet = {10},minlen = 10,maxlen = 10

j = i + 1 = 1,如果mySet将有12,则为false,

因此,将12插入mySet中,找到最大值12和10,最小值,并将12存储到maxlen中,将10存储到minlen中,然后检查maxlen-minlen是否等于j – i,但这是错误的。

j = 2,如果mySet将有13,则为false,

因此,将13插入mySet并找到最大值13和12,然后将13存储到maxlen中,将10存储到minlen中,然后检查maxlen-minlen是否等于j – i为假。

参见
最小元素正好重复K次

j = 3,如果mySet将有11,则为false,

因此,将11插入mySet并找到11和10的最大值,然后将13存储到maxlen中,将10存储到minlen中,然后检查maxlen-minlen是否等于j –我现在为真,因为13-10等于3-0。 因此,通过找出maxLength和maxlen-minlen + 1 max(1,13-10 + 1)的最大值来更新maxLength,发现有4和4存储在maxLength中,它将继续遍历数组并设置直到找到比连续子数组更长的长度。

输出:4

代码  

C ++代码查找具有连续元素的最大子数组的长度

#include<set>
#include<iostream>

using namespace std;

int getLongestLength(int arr[], int l)
{
    int maxLength = 1;
    for (int i=0; i<l-1; i++)
    {
        set<int> mySet;
        mySet.insert(arr[i]);
        int minlen = arr[i], maxlen = arr[i];

        for (int j=i+1; j<l; j++)
        {
            if (mySet.find(arr[j]) != mySet.end())
                break;

            mySet.insert(arr[j]);
            minlen = min(minlen, arr[j]);
            maxlen = max(maxlen, arr[j]);

            if (maxlen - minlen == j - i)
                maxLength = max(maxLength, maxlen - minlen + 1);
        }
    }
    return maxLength;
}
int main ()
{
    int arr[] = {10, 12, 13, 11, 8, 10};
    int l = sizeof(arr) / sizeof(arr[0]);
    cout << "Length of the Longest contiguous Sub-Array is: " << getLongestLength(arr, l);
    return 0;
}
Length of the Longest contiguous Sub-Array is: 4

Java代码查找具有连续元素的最大子数组的长度

import java.util.HashSet;

class largestSubArrayContiguousElements
{
    public static int getLongestLength(int arr[])
    {
        int l = arr.length;
        int maxLength = 1;

        for (int i=0; i< l-1; i++)
        {
            HashSet<Integer> mySet = new HashSet<>();
            mySet.add(arr[i]);

            int min = arr[i];

            int max = arr[i];

            for (int j=i+1; j<l; j++)
            {
                if (mySet.contains(arr[j]))
                    break;

                mySet.add(arr[j]);
                min = Math.min(min, arr[j]);
                max = Math.max(max, arr[j]);

                if (max-min == j-i)
                    maxLength = Math.max(maxLength, max-min+1);
            }
        }
        return maxLength;
    }
    public static void main (String[] args)
    {
        int arr[] = {10, 12, 13, 11, 8, 10};
        System.out.println("Length of the Longest contiguous SubArray is: "+getLongestLength(arr));
    }
}
Length of the Longest contiguous SubArray is: 4

复杂度分析  

时间复杂度

2) 哪里 “ n” 是数组中元素的数量。

参见
当元素不限于范围时,在给定数组中查找重复项

空间复杂度

O(N) 哪里 “ n” 是数组中元素的数量。