차이 어레이 | O (1)의 범위 업데이트 쿼리

난이도 하드
자주 묻는 질문 아르 세슘 코드네이션 지시 Expedia 구글 퀄컴
배열 쿼리 문제조회수 25

당신은 주어진 정수 정렬 두 가지 유형의 쿼리, 하나는 범위에 주어진 숫자를 추가하는 것이고 다른 하나는 전체 배열을 인쇄하는 것입니다. 문제“차이 배열 | O (1)의 범위 업데이트 쿼리”에서는 O (1)에서 범위 업데이트를 수행해야합니다.

arr[] = {20, 30, 25, 50}

Update(0, 1, 10)

print()

update(0, 2, 20)

update(2, 3, 30)

print()
(30 40 25 50) (50 60 75 80)

설명

10이 20과 30에 추가되므로 어레이는 {30, 40, 25, 50}이됩니다.

그런 다음 전체 배열을 인쇄합니다.

20은 30, 40, 25에 추가되므로 어레이는 {50, 60, 45, 50}이됩니다.

10이 45과 50에 추가되므로 어레이는 {50, 60, 75, 80}이됩니다.

그런 다음 다시 전체 배열을 인쇄합니다.

두 세트의 값은 쿼리를 수행 한 후 인쇄됩니다.

차이 어레이 | O (1)의 범위 업데이트 쿼리

 

차이 배열에 대한 알고리즘

  1. 주어진 배열과 같은 크기의 배열을 만듭니다.
  2. 첫 번째 인덱스는 주어진 배열의 첫 번째 요소로 초기화하고 마지막 인덱스는 0으로 초기화합니다. 그리고 다른 모든 인덱스는 현재와 이전 요소의 차이로 채워집니다.
  3. 모든 업데이트 쿼리에 대해 생성 된 배열의 지정된 왼쪽 인덱스에 값 X를 더하고 생성 된 배열의 오른쪽 인덱스에서 X를 뺍니다.
  4. 모든 인쇄 쿼리에 대해 먼저 공식 A [i] = D [i] + A [i-1]을 사용하여 입력 배열을 채 웁니다. 그런 다음 값을 인쇄하십시오.

설명

배열과 숫자 및 두 가지 유형의 쿼리가 제공됩니다. 따라서 두 가지 유형의 쿼리를 수행해야합니다. 우리는 숫자 X와 함께 범위를 나타내는 두 개의 숫자를 갖게 될 것입니다. 따라서 우리의 임무는 주어진 범위 사이의 모든 인덱스에 숫자 X를 더하는 것입니다. 방법 중 하나는 순진한 접근 방식을 사용하는 것입니다. 이를 위해 값을 업데이트해야 할 때마다 주어진 배열을 탐색하십시오.

여기서 더 나은 솔루션은 차이점을 저장하는 추가 배열을 만드는 것입니다. 이것이 차이 배열이라고 불리는 이유입니다. 먼저 차이 배열의 첫 번째 요소를 입력 배열의 첫 번째 요소로 초기화합니다. 그런 다음 차이 배열의 마지막 요소를 0에 할당합니다. 그 후 배열을 탐색하고 차이 배열의 현재 인덱스에 현재 값과 이전 값의 차이를 저장합니다.

업데이트 쿼리를 받으면 값을 범위로 가져옵니다. 우리와 함께 번호도 제공됩니다. 그런 다음 차이 배열에서 범위의 왼쪽 인덱스에 해당 숫자를 추가합니다. 마찬가지로 차이 배열의 오른쪽 인덱스에서 값 X를 뺍니다. 배열을 인쇄하기 위해 배열을 순회하고 인덱스 값이 XNUMX 인 경우 주어진 배열의 값을 생성 한 배열로 업데이트합니다. 그렇지 않으면 생성 된 배열과 주어진 배열의 이전 값의 합을 얻습니다. 특정 색인에 대해 해당 값을 인쇄하십시오.

암호

차이 배열을위한 C ++ 구현

#include<iostream>

using namespace std;

void buildArray(int arr[], int dummyArray[], int n)
{
    dummyArray[0] = arr[0];
    dummyArray[n] = 0;
    for (int i = 1; i < n; i++)
        dummyArray[i] = arr[i] - arr[i - 1];
}

static void update(int dummyArray[], int l, int r, int x)
{
    dummyArray[l] += x;
    dummyArray[r + 1] -= x;
}

void printArray(int arr[], int dummyArray[], int n)
{
    for (int i = 0; i <n; i++)
    {

        if (i == 0)
            arr[i] = dummyArray[i];
        else
            arr[i] = dummyArray[i] + arr[i - 1];

        cout<<arr[i] << " ";
    }

    cout<<endl;
}

int main()
{
    int arr[] = {20,30,25,50};
    int n = sizeof(arr)/sizeof(arr[0]);

    int dummyArray[n + 1];
    buildArray(arr, dummyArray, n);

    update(dummyArray, 0, 1, 10);
    printArray(arr, dummyArray, n);
    update(dummyArray, 0, 2, 20);
    update(dummyArray, 2, 3, 30);

    printArray(arr, dummyArray,n);
    return 0;
}
30 40 25 50
50 60 75 80

차이 배열을위한 Java 구현

class differenceArray
{
    static void buildArray(int arr[], int dummyArray[])
    {

        int n = arr.length;

        dummyArray[0] = arr[0];
        dummyArray[n] = 0;
        for (int i = 1; i < n; i++)
            dummyArray[i] = arr[i] - arr[i - 1];
    }
    
    static void update(int dummyArray[], int left, int right, int x)
    {
        dummyArray[left] += x;
        dummyArray[right + 1] -= x;
    }
    
    static int printArray(int arr[], int dummyArray[])
    {
        for (int i = 0; i < arr.length; i++)
        {
            if (i == 0)
                arr[i] = dummyArray[i];
            else
                arr[i] = dummyArray[i] + arr[i - 1];

            System.out.print(arr[i] + " ");
        }

        System.out.println();

        return 0;
    }
    
    public static void main(String[] args)
    {
        int arr[] = {20, 30, 25, 50};
        int n = arr.length;
        int dummyArray[] = new int[n + 1];

        buildArray(arr, dummyArray);

        update(dummyArray, 0, 1, 10);
        printArray(arr, dummyArray);
        update(dummyArray, 0, 2, 20);
        update(dummyArray, 2, 3, 30);

        printArray(arr, dummyArray);
    }
}
30 40 25 50
50 60 75 80

복잡성 분석

시간 복잡성

O (q) 어디에 "Q" 업데이트 쿼리가 수행 할 때 실행되는 인쇄 쿼리의 수입니다. O (1) 시간.

공간 복잡성

O (N) 어디에 "엔" 배열의 요소 수입니다. 추가 차이 배열을 생성했기 때문에 선형 공간 복잡성이 있습니다.

Translate »