범위의 모든 요소가 배열에 존재하도록 추가 할 요소


난이도 중급
자주 묻는 질문 그레이 오렌지 쿨리 자 스냅 딜 Synopsys 테라 데이타 타임즈 인터넷
배열 해시 해싱 정렬

문제 정책

"범위의 모든 요소가 배열에 존재하도록 추가 할 요소"는 정수 배열이 제공됨을 나타냅니다. 문제 설명은 모든 요소가 배열에서 적어도 한 번을 포함하여 [X, Y] 범위에 있도록 배열에 추가 할 요소의 개수를 알아 내도록 요청합니다. X와 Y는 각각 배열의 최소 및 최대 수입니다.

arr[] = {4,5,7,9,11}
3

설명 : X와 Y는 4와 11 (각각 최소 및 최대 숫자)이며이 숫자 범위 내에서 3, 6 및 8이 누락되었습니다.

범위의 모든 요소가 배열에 존재하도록 추가 할 요소

arr[] = {2,4,6,7}
2

설명 : X와 Y는 2와 7 (각각 최소 및 최대 숫자)이며,이 숫자 범위 내에서 2 만 3과 5가 누락되었습니다.

범위의 모든 요소가 배열에 존재하도록 추가 할 요소를 찾는 알고리즘

1. Declare a Set.
2. Set output to 0, minValue to the maximum value of integer and maxValue to the minimum value of an integer.
3. Traverse the array and put all the values into the set and simultaneously find out the maximum and the minimum number of an array and store it to the maxValue and minValue respectively.
4. Traverse the array again, from minValue to maxValue.
5. Check if the map doesn’t contain any of the elements in traversal, then, increase the count of output.
6. Return output.

설명

우리는이 정수 정렬. 문제는 배열에 추가 할 요소의 수를 찾는 것입니다. 모든 요소가 배열의 최대 및 최소 수 범위에 있도록하여 요소가 한 번 이상 발생하지 않도록합니다.

Set 선언, Set에는 고유 한 요소를 한 번만 저장하는 속성이 있습니다. 즉, 공통 요소를 제거하고 고유 한 요소 만 저장합니다. 그래서 우리는 그 사건을 처리 할 수있을 것입니다. 이제 모든 배열 요소를 집합에 삽입합니다. 동시에 최대 및 최소 요소를 찾을 수 있습니다. 따라서 최대 및 최소를 찾기 위해 추가 순회를 수행 할 필요가 없습니다. 결국 범위 내에서 누락 된 요소의 개수를 알아 내면됩니다. 따라서 숫자 만 세면됩니다. 그리고 우리는 숫자 자체를 다룰 필요가 없습니다.

이제 배열의 최소값부터 배열의 최대 값까지 배열을 순회합니다. 이것이 우리에게 필요한 유일한 범위이기 때문입니다. 범위 내의 각 숫자를 선택하고 세트에 해당 범위의 값이 없는지 확인합니다. 세트에 현재 범위 값이 포함되어 있지 않으면 출력 수를 늘릴 것입니다. 그리고 집합에 범위 값이 없을 때마다 출력 값을 1 씩 증가시킵니다. 언급 된 코드에서 최소값이 4이고 최대 값이 11이고 그 사이에 6,8과 10이 (4,11) 범위 내에서 누락 된 것처럼 이러한 요소도 배열에 존재하지 않으므로 해당 요소 수를 계산합니다. 마지막으로 해당 출력을 반환합니다.

암호

범위의 모든 요소가 배열에 존재하도록 추가 할 요소를 찾는 C ++ 코드

#include<iostream>
#include<unordered_set>

using namespace std;

int getCountMissingNumber(int arr[], int n)
{
    unordered_set<int> SET;
    int output = 0;
    int maxValue = INT_MIN;
    int minValue = INT_MAX;

    for (int i = 0; i < n; i++)
    {
        SET.insert(arr[i]);
        if (arr[i] < minValue)
            minValue = arr[i];
        if (arr[i] > maxValue)
            maxValue = arr[i];
    }
    for (int a = minValue; a <= maxValue; a++)
    {
        if (SET.find(a) == SET.end())
        {
            output++;
        }
    }
    return output;
}
int main()
{
    int arr[] = {4,5,7,9,11 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << getCountMissingNumber(arr, n);
    return 0;
}
3

범위의 모든 요소가 배열에 존재하도록 추가 할 요소를 찾는 Java 코드

import java.util.HashSet;

class NumberBwRange
{
    public static int getCountMissingNumber(int arr[], int n)
    {
        HashSet<Integer> SET = new HashSet<>();
        int output = 0;
        int maxValue = Integer.MIN_VALUE;
        int minValue = Integer.MAX_VALUE;

        for (int i = 0; i < n; i++)
        {
            SET.add(arr[i]);
            if (arr[i] < minValue)
                minValue = arr[i];
            if (arr[i] > maxValue)
                maxValue = arr[i];
        }

        for (int i = minValue; i <= maxValue; i++)
            if (!SET.contains(i))
                output++;
        return output;
    }
    public static void main(String[] args)
    {
        int arr[] = { 4,5,7,9,11 };
        int n = arr.length;
        System.out.println(getCountMissingNumber(arr, n));
    }
}
3

복잡성 분석

시간 복잡성

O (최대-최소 + 1) 어디에 "최대" 및 "분" 있는 최고최저한의 배열의 값. 최소 요소에서 최대 요소로 이동했기 때문입니다. 그렇기 때문에 최악의 경우이 값이 N 요소를 초과 할 수 있습니다. 따라서 max-min + 1이 N보다 클 수 있기 때문입니다. 시간 복잡도는 O (max-min + 1)입니다. 여기서 max는 최대 요소를 나타내고 min은 최소 요소를 나타냅니다.

공간 복잡성

의 위에) 어디에 "엔" 배열의 요소 수입니다. N 개의 요소 만 저장하기 때문에 알고리즘은 선형 공간 복잡성을 갖습니다.