주어진 범위의 값을 가진 배열 요소의 개수에 대한 쿼리  


난이도 하드
자주 묻는 질문 Coursera 드 쇼 구글 알레그로 스냅 딜 타임즈 인터넷 Yahoo
배열 비트 쿼리 문제

문제 정책  

"주어진 범위의 값을 가진 배열 요소의 개수에 대한 쿼리"문제는 정수 정렬 두 개의 숫자 x와 y. 문제 설명은 주어진 x와 y 사이에있는 배열에있는 숫자의 개수를 알아 내도록 요청합니다.

예  

arr[]={2,4,6,8,1,10}
x = 2, y = 8
4

설명

배열에는 4 개의 요소가 있으므로 2와 4 사이에 6, 8, 2 및 8이 있습니다.

주어진 범위의 값을 가진 배열 요소의 개수에 대한 쿼리

arr[]={2,4,6,8,1,10}
x = 5, y = 10
3

설명

배열에는 3 개의 요소 (6, 8, 10)가 있으므로 5와 10 사이에 포함됩니다.

암호알고리즘  

  1. 종류 배열
  2. 이진 검색을 사용하여 요소 y의 배열에서 더 큰 인덱스를 찾고 더 큰 인덱스를 반환합니다.
  3. 이진 검색을 사용하여 요소 x 배열의 더 작은 인덱스를 찾고 더 작은 인덱스를 반환합니다.
  4. 더 큰 지수와 더 작은 지수의 차이를 더한 값으로 반환합니다.

설명  

정수 배열과 두 개의 숫자 x와 y를 제공했습니다. 주어진 x와 y 사이에있는 주어진 배열에 존재하는 총 수를 알아 내도록 요청했습니다. 기본적으로 "x"보다 큰 숫자의 개수를 찾아야합니다. 그리고 "y"보다 작은 숫자의 개수입니다. 우리는 배열을 정렬 할 것입니다. 그 뒤에있는 이유는 이진 검색 방법을 사용하기 때문입니다. 그것도 수정되고 있습니다.

참조
두 배열 모두에 공통 요소가 없도록 최소 요소 수 제거

숫자의 색인을 가져옵니다 y 이진 검색을 사용하여 배열에서. 이진 검색에서 우리는 y가있는 인덱스를 찾으려고합니다. low 값이 high 값보다 작거나 같을 때까지 루프를 계속합니다. 일반적으로 low는 0 번째 인덱스이고 high는 배열 인덱스에 대해 이진 검색을 수행하기 때문에 배열의 마지막 인덱스입니다. 이진 검색을 사용하면 각 쿼리에 대한 로그 시간 복잡도에서 주어진 범위의 값을 가진 배열 요소의 개수에 대한 쿼리에 답할 수 있습니다.

낮은 값과 높은 값의 중간 값을 얻고 array [mid]에있는 요소가 x보다 큰지 확인합니다. 이것이 사실이면 high 값을 mid-1로 업데이트합니다. 그렇지 않으면 낮음에서 중간 +1의 값을 업데이트합니다. 요소 y에도 동일하게 적용됩니다. 그러나이 경우 더 큰 인덱스를 찾고 array [mid]가 y보다 큰지 확인하는 대신 확인합니다. 그런 다음 array [mid]가 y보다 작은 지 계속 확인하고 low에서 mid + 1로, high에서 mid-1로 업데이트합니다.

두 인덱스를 모두 크고 작은 것으로 가져 와서 차이를 반환하고 여기에 1을 더합니다. 이것은 반환되는 우리의 필수 답변입니다. 주어진 범위의 값을 가진 배열 요소의 개수에 대한 쿼리에 답하고 싶었습니다.

암호  

주어진 범위 내에서 배열 요소의 개수를 찾는 C ++ 코드

#include<iostream>
#include<algorithm>

using namespace std;

int smallerElement(int arr[], int n, int x)
{
    int low = 0, high = n - 1;
    while (low <= high)
    {
        int mid = (low + high) / 2;
        if (arr[mid] >= x)
            high = mid - 1;
        else
            low = mid + 1;
    }
    return low;
}
int greaterElement(int arr[], int n, int y)
{
    int low = 0, high = n - 1;
    while (low <= high)
    {
        int mid = (low + high) / 2;
        if (arr[mid] <= y)
            low = mid + 1;
        else
            high = mid - 1;
    }
    return high;
}
int countInRange(int arr[], int n, int x, int y)
{
    int count = 0;
    count = greaterElement(arr, n, y) - smallerElement(arr, n, x) + 1;
    return count;
}
int main()
{
    int arr[] = {2,4,6,8,1,10 };
    int n = sizeof(arr) / sizeof(arr[0]);

    sort(arr, arr + n);

    int i = 2, j = 8;
    cout << countInRange(arr, n, i, j) << endl;

    i = 5, j = 10;
    cout << countInRange(arr, n, i, j) << endl;
    return 0;
}
4
3

주어진 범위 내에서 배열 요소의 수를 찾는 Java 프로그램

import java.io.*;
import java.util.Arrays;

class NumberOfElements
{
    private static int countInRange(int arr[], int n, int x, int y)
    {
        int count = 0;
        count = greaterElement(arr, n, y) -
                smallerElement(arr, n, x) + 1;
        return count;
    }
    
    private static int smallerElement(int arr[], int n, int x)
    {
        int low = 0, high = n - 1;
        while (low <= high)
        {
            int mid = (low + high) / 2;
            if (arr[mid] >= x)
                high = mid - 1;
            else
                low = mid + 1;
        }
        return low;
    }
    
    private static int greaterElement(int arr[], int n, int y)
    {
        int low = 0, high = n - 1;
        while (low <= high)
        {
            int mid = (low + high) / 2;
            if (arr[mid] <= y)
                low = mid + 1;
            else
                high = mid - 1;
        }
        return high;
    }

    public static void main (String[] args)
    {
        int arr[] = {2,4,6,8,1,10 };
        int n = arr.length;

        Arrays.sort(arr);

        int x = 2, y = 8;
        System.out.println( countInRange(arr, n, x, y)); ;

        x = 5;
        y = 10;
        System.out.println( countInRange(arr, n, x, y));
    }
}
4
3

복잡성 분석  

시간 복잡성

각 쿼리 실행 시간은 O (로그 n) 정렬을 위해 배열을 한 번 O (n log n).

참조
주어진 두 세트가 분리되었는지 확인하는 방법은 무엇입니까?

공간 복잡성

O (N) 어디에 "엔" 배열의 요소 수입니다. 우리가 고려한 공간은 배열을 정렬하는 동안 차지하는 공간 때문입니다. 입력을 저장하는 데 필요한 공간은 "주어진 범위의 값을 가진 배열 요소의 개수에 대한 쿼리"문제에서 고려되지 않습니다.