주어진 범위에서 동일한 요소가있는 인덱스 수

난이도 중급
자주 묻는 질문 그레이 오렌지 과연 운영 클립 스냅 딜 Yahoo
배열 쿼리 문제조회수 17

당신은 주어진 정수 정렬, q 쿼리 및 범위 (왼쪽 및 오른쪽). "주어진 범위에서 동일한 요소를 가진 인덱스 수"는 왼쪽 <= i <오른쪽과 같은 방식으로 정수의 총 개수를 알아 내도록 말합니다.i = Aj + 1.

arr[] = {2, 2, 3, 3, 3, 4, 4, 4, 4}
Query = 2
Left = 2, right = 6
Left = 4, right = 8
3
3

설명

query1의 경우, 여기서 left = 2, right = 6

arr[2]=arr[3], arr[3]=arr[4], arr[5]=arr[6]

카운트는 3입니다.

query2의 경우, 왼쪽 = 4, 오른쪽 = 8

arr[5]=arr[6], arr[6]=arr[7], arr[7]=arr[8]

카운트는 3입니다.

주어진 범위에서 동일한 요소가있는 인덱스 수

 

암호알고리즘

  1. 배열을 만듭니다.
  2. 배열을 통과합니다.
  3. 현재 배열 요소가 다음 요소와 같으면 생성 된 배열의 요소를 1로 표시합니다.
  4. 인덱스가 0이 아니면 arrayDummy의 현재 배열 요소와 다음 배열 요소의 합을 arrayDummy [i]에 저장합니다.
  5. 쿼리를 풀고 왼쪽 위치가 0이면 arrayDummy [right-1]을 반환하고 그렇지 않으면 arrayDummy [right-1]과 arrayDummy [left-1]의 차이를 반환합니다.

설명

우리는 주어진 정수 배열 및 범위를 왼쪽과 오른쪽으로 지정합니다. 인접한 요소가 서로 같은 방식으로 인덱스 수를 알아 내도록 요청받습니다. 두 개의 다른 인덱스를 가진 두 개의 동일한 인접 요소를 찾으면 1을 세는 식입니다. 그런 다음 최대 크기의 배열을 만듭니다. 주어진 조건을 만족하는 인덱스를 세는 함수를 만들었습니다. 조건은 인접한 두 요소가 서로 동일하다는 것입니다.

배열을 처음부터 배열 길이보다 작은 배열로 순회합니다. 그런 다음 배열의 현재 요소가 배열의 다음 요소와 같은지 확인합니다. 조건이 참인 경우. 그런 다음 현재 인덱스의 해당 값을 1로 표시합니다. 인접한 요소가 동일한 지 알 수 있기 때문에 1을 표시합니다. 그런 다음 각 쌍은 카운트 1로 간주되고 이전 쌍의 공통 요소가 하나 인 다음 쌍은 2로 계산됩니다. n 쌍이 같으면 n-1의 개수가 있습니다. 또한 인덱스 값이 0이 아닌 경우. 첫 번째 요소가 아닌 경우 순회하는 동안 의미합니다. arrayDummy 현재 요소와 이전 요소의 합을 arrayDummy의 현재 인덱스에 저장합니다.

범위의 왼쪽 인덱스가 0이면 주어진 각 쿼리에 대해 arrayDummy [right – 1]을 반환합니다. 그렇지 않으면 0이 아니면 단순히 arrayDummy [right – 1]와 arrayDummy [left – 1]의 차이를 반환합니다.

암호

주어진 범위에서 동일한 요소가있는 인덱스 수를 계산하는 C ++ 코드

#include <iostream>

using namespace std;

int arrayDummy[100];

void getNumbers(int a[], int n)
{
    for (int i = 0; i < n - 1; i++)
    {
        if (a[i] == a[i + que
            arrayDummy[i] = 1;

        if (i != 0)
            arrayDummy[i] += arrayDummy[i - 1];
    }
}

int solveQuery(int l, int r)
{
    if (l == 0)
        return arrayDummy[r - 1];
    else
        return arrayDummy[r - 1] - arrayDummy[l - 1];
}

int main()
{
    int arr[] = { 2,2,3,3,3,4,4,4,4};
    int n = sizeof(arr) / sizeof(arr[0]);

    getNumbers(arr, n);

    int left, right;

    left = 2;
    right = 6;

    cout << solveQuery(left, right) << endl;
    left = 4;
    right = 8;
    cout << solveQuery(left, right) << endl;
    return 0;
}
3
3

주어진 범위에서 동일한 요소가있는 인덱스 수를 계산하는 Java 코드

class IndexElementsEqual
{
    static int arrayDummy[] = new int[1000];

    public static void getNumbers(int arr[], int n)
    {
        for (int i = 0; i < n-1; i++)
        {
            if (arr[i] == arr[i + 1])
                arrayDummy[i] = 1;

            if (i != 0)
                arrayDummy[i] += arrayDummy[i - 1];
        }
    }
    public static int solveQuery(int left, int right)
    {
        if (left == 0)
            return arrayDummy[right - 1];
        else
            return arrayDummy[right - 1] - arrayDummy[left - 1];
    }
    public static void main(String args[])
    {
        int arr[] = {2,2,3,3,3,4,4,4,4};
        int n = arr.length;

        getNumbers(arr, n);

        int left, right;

        left = 2;
        right = 6;

        System.out.println(solveQuery(left, right));
        left = 4;
        right = 8;
        System.out.println(solveQuery(left, right));
    }
}
3
3

복잡성 분석

시간 복잡성

 O (1) 모든 쿼리에 대해 O (N) 사전 컴퓨팅을 위해.

공간 복잡성

O (N) 어디에 "엔" 배열의 요소 수입니다. 이 공간은 arrayDummy 생성에 필요합니다.

Translate »