배열에 존재하는 최대 연속 수


난이도 쉽게
자주 묻는 질문 Accolite 어도비 벽돌 아마존 Fourkites MAQ
배열 해시

문제 정책

배열이 있다고 가정합니다. 정수 "배열에 존재하는 최대 연속 번호"문제는 배열에 흩어져있을 수있는 연속 번호의 최대 개수를 알아 내도록 요구합니다.

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.

설명

주어진 정수 정렬, 우리는 배열에 존재하는 가장 높은 연속 숫자 수를 찾아야합니다. 우리는 세트. Set는 유사한 요소를 제거하는 기능을 제공합니다. 따라서 공통 요소를 처리하는 것에 대해 걱정할 필요가 없습니다. 자동으로 처리됩니다.

배열의 모든 값을 Set에 더할 것입니다. 나중에 우리는 연속 된 숫자도 확인할 것이기 때문입니다. 배열을 다시 탐색하여 각 요소를 선택하고 지도 arr [i]가 있습니다. true이면 해당 요소를 임시 변수로 선택하고 맵에 해당 temp가 포함되어 있는지 다시 확인하고 true이면 temp 값을 1 씩 늘린 다음 다시 확인합니다. 다시 증가시키고 맵에 증가 된 값이 없을 때까지 계속합니다. 이제이 루프에서 나올 때지도에있는 현재 배열 요소의 가장 많이 증가 된 값이 될 것입니다. 또한 1만큼 증가시켜 연속적인 숫자가 될 것입니다.

이제 출력의 최대 값과 temp-arr [i]의 차이를 알아 내야합니다.이 차이가 카운트의 잘못된 수를 제공한다고 생각하지 마십시오. 루프, 우리는 존재하는 연속 번호의 정확한 개수를 얻을 것입니다. 그런 다음 출력과 temp-arr [i] (출력, 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) 어디에 "엔" 배열의 요소 수입니다. 삽입, 삭제, 검색 작업이 일정한 시간에 가능한 HashSet을 사용했기 때문입니다.

공간 복잡성

O (N) 어디에 "엔" 배열의 요소 수입니다. 집합에 N 개의 요소를 저장 했으므로 선형 공간 복잡성이 있습니다.

참고