配列に存在する最大連続数


難易度 簡単に
よく聞かれる アコライト Adobe Amazon (アマゾン) フォーカイテス MAQ
配列 ハッシュ

問題文

あなたがの配列を持っていると仮定します 整数 サイズNの問題。「配列に存在する最大連続数」の問題は、配列に散在する可能性のある連続数の最大数を見つけることを求めています。

arr[] = {2, 24, 30, 26, 99, 25}
3

説明: 連番は⇒24、25、26(3個セット)です。

arr[] = { -8, 9 , -1, -6, -5}
2

説明: 連番は⇒-6、-5(2個セット)です。

アルゴリズム

1. Declare a set.
2. Do traversing of the array, and insert all the values of array into the Set.
3. Set output to 0.
4. Traverse the array from i=0, to i<n(length of the array).
  1. Check if Set contains the arr[i].
    1. If true, then pick the current array element and store it to temp.
  2. While Set contains the temp, repeatedly increases the values of temp.
  3. Find out the maximum between output and temp-arr[i] and store it into the output.
5. Return output.

説明

与えられた 整数 配列、配列に存在する連続番号の最大数を見つける必要があります。 を使用します セッションに。 セットは、同様の要素を削除する機能を提供します。 したがって、共通要素の処理について心配する必要はありません。自動的に処理されます。

配列のすべての値をセットに追加します。 後で、連続番号もチェックする予定です。 配列を再度トラバースし、各要素を選択して、 地図 そのarr [i]がある場合、trueの場合、その要素を一時変数に選択し、マップにそのtempが含まれているかどうかを再度確認し、trueの場合、tempの値を1増やしてから、もう一度確認します。再びそれを増やし、マップにその増分値がなくなるまでこれを続けます。 ここで、このループから抜け出すと、マップに存在する現在の配列要素の最大の増分値になります。また、1のカウントで増加するため、これも連続した数値になります。

ここで、出力の最大値とtemp-arr [i]の差を見つける必要があります。この差が間違ったカウント数を与えるとは思わないでください。これは、温度の増分値を取得するためです。ループ、存在する連続した数の正しいカウントを取得します。 次に、出力とtemp-arr [i]の差(output、temp-arr [i])の間の最大値を格納します。 Arr [i]は、一連の連続する数値と温度の開始点であり、終了点です。 これらの手順は、アレイ全体をトラバースした後に最大出力が見つかるまで繰り返されます。

配列に存在する最大連続数

製品の導入

配列に存在する最大連続数を見つけるためのC ++プログラム

#include<iostream>
#include<unordered_set>

using namespace std;

int getMaxConsecutiveNumber(int arr[], int n)
{
    unordered_set<int> SET;
    for (int i = 0; i < n; i++)
        SET.insert(arr[i]);

    int output = 0;
    for (int i = 0; i < n; i++)
    {
        if (SET.find(arr[i] - 1) == SET.end())
        {
            int temp = arr[i];

            while (SET.find(temp) != SET.end())
                temp++;

            output = max(output, temp - arr[i]);
        }
    }
    return output;
}
int main()
{
    int arr[] = {2, 24, 30, 26, 99, 25 };
    int n = sizeof(arr) / sizeof(int);
    cout << "Largest Set found : "<<getMaxConsecutiveNumber(arr, n)<< endl;
    return 0;
}
Largest Set found : 3

配列に存在する最大連続数を見つけるJavaプログラム

import java.util.HashSet;

class LargestConsecutiveSet
{
    public static int getMaxConsecutiveNumber(int arr[], int n)
    {
        HashSet<Integer> SET = new HashSet<Integer>();
        for (int i = 0; i < n; i++)
        {
            SET.add(arr[i]);
        }
        int output = 0;
        for (int i = 0; i < n; i++)
        {
            if(SET.contains(arr[i]))
            {
                int temp = arr[i];
                while (SET.contains(temp))
                    temp ++;

                output = Math.max(output, temp - arr[i]);
            }
        }
        return output;
    }
    public static void main(String[] args)
    {
        int arr[] = {2, 24, 30, 26, 99, 25};
        int n = arr.length;
        System.out.println("Largest Set found : "+getMaxConsecutiveNumber(arr, n));
    }
}
Largest Set found : 3

配列に存在する最大連続数を見つけるための複雑さの分析

時間の複雑さ

O(N) where 「n」 配列内の要素の数です。 挿入、削除、検索操作を一定時間で行えるHashSetを使用しているためです。

スペースの複雑さ

O(N) where 「n」 配列内の要素の数です。 セットにN個の要素を格納したため、線形空間の複雑さが増しました。

参照