查詢子數組中不同元素的數量


難度級別
經常問 亞馬遜 谷歌 Microsoft微軟 神諭 尤伯杯
排列 段樹

我們給了 排列 整數和多個查詢,我們必須找出給定範圍內所有不同元素的數量,查詢由左右兩個數字組成,這是給定範圍,必須在給定範圍內找出不同元素的數量。

輸入:

arr [] = {2,3,4,1,1}

0,4

1,3

2,4

輸出:

電話: 4 3 2

說明:

在第一個查詢中,a [0…4]中不同整數的數量為4(4,3,2,1)。 在第二個查詢中,a [1..3]中不同整數的數目為3(4,3,1)。 在第三個查詢中,a [2..4]中不同整數的數量為2(1、4)。

找出給定範圍內我們擁有的所有不同元素的數量,

算法

  1. 製作對像數組,並在每個位置將值分別標記為left,right和與每個值關聯的索引 對象.
  2. 根據給定的正確值(範圍)對查詢數組進行排序。
  3. 創建一個數組binaryIndTree []。
  4. 開始遍歷給定的數組,同時遍歷給定的查詢,
  5. 檢查受訪數組[a [i]]是否為-1。
  6. 如果為false,則在索引visitedArray [a [i]]處將值為-1的binaryIndTree數組更新。
  7. 設置VisitedArray [a [i]] = i,並在索引i處將值為1的binaryIndTree數組binaryIndTree數組更新。
  8. 將counter設置為0,並開始遍歷直到計數器小於查詢數量,並且直到查詢right值等於i。
  9. 對於對象的每個查詢索引,數組將值查詢索引更新為查詢的右值和查詢的左值之差。
  10. 打印每個定義的查詢的所有結果。

解釋

我們將創建一個對像數組,以便使用該對像數組鏈接左,右,索引或查詢數。 然後,我們將對該查詢對象進行排序,以使查詢數組按“正確”值的升序排序,這意味著具有“正確”值最小的查詢將排在第一位。

現在,創建一個為binaryIndTree的數組。 用0初始化數組的所有值,然後創建一個max大小為1000001的數組。將此數組的所有值初始化為-1,並將size查詢的輸出的最後一個數組初始化,因為存在相同數量的輸出為查詢數。 計數器的值應設置為0。現在我們開始遍歷數組,並檢查VisitedArray [arr [i]] = -1,如果發現它為true,則用值-1更新binaryIndTree的值。 在將值VisitedArray [arr [i]]更新為i之後,再次用值1更新binaryIndTree,無論上述條件是否為真,都可以這樣做。

在此循環內,開始更新數組,直到數組的值小於查詢數q的值為止。 用查詢的右值和查詢的左值之差更新輸出數組,並在每個索引處更新,請記住,當我們創建與查詢數量相同的索引時。 並增加櫃檯的價值。 最後,打印輸出數組中的所有值。

履行

C ++程序,用於查詢子數組中不同元素的數量

#include<bits/stdc++.h>

using namespace std;

const int MAX = 1000001;

struct Query
{
    int left, right, index;
};

bool compare(Query x, Query y)
{
    return x.right < y.right;
}

void update(int index, int val, int binaryIndTree[], int n)
{
    for (; index <= n; index += index&-index)
        binaryIndTree[index] += val;
}

int query(int index, int binaryIndTree[], int n)
{
    int sum = 0;
    for (; index>0; index-=index&-index)
        sum += binaryIndTree[index];
    return sum;
}

void getQueryOutput(int arr[], int n, Query queries[], int q)
{
    int binaryIndTree[n+1];
    memset(binaryIndTree, 0, sizeof(binaryIndTree));

    int visitedArray[MAX];
    memset(visitedArray, -1, sizeof(visitedArray));

    int output[q];
    int counter = 0;
    for (int i=0; i<n; i++)
    {
        if (visitedArray[arr[i]] !=-1)
            update (visitedArray[arr[i]] + 1, -1, binaryIndTree, n);

        visitedArray[arr[i]] = i;
        update(i + 1, 1, binaryIndTree, n);

        while (counter < q && queries[counter].right == i)
        {
            output[queries[counter].index] = query(queries[counter].right + 1, binaryIndTree, n)- query(queries[counter]. left, binaryIndTree, n);
            counter++;
        }
    }
    for (int i=0; i<q; i++)
        cout << output[i] << endl;
}

int main()
{
    int a[] = { 2,3,4,1,1};
    int n = sizeof(a)/sizeof(a[0]);
    Query queries[3];
    queries[0].left = 0;
    queries[0].right = 4;
    queries[0].index = 0;
    queries[1].left = 1;
    queries[1].right = 3;
    queries[1].index = 1;
    queries[2].left = 2;
    queries[2].right = 4;
    queries[2].index = 2;
    int q = sizeof(queries)/sizeof(queries[0]);
    sort(queries, queries+q, compare);
    getQueryOutput(a, n, queries, q);
    return 0;
}
4
3
2

Java程序,用於查詢子數組中不同元素的數量

import java.util.Arrays;
import java.util.Comparator;

class distinctElementsQuery
{
    static int MAX = 1000001;

    static class Query
    {
        int l, r, index;
    }

    static void update(int index, int val, int binaryIndTree[], int n)
    {
        for (; index <= n; index += index & -index)
            binaryIndTree[index] += val;
    }
    static int query(int index, int binaryIndTree[], int n)
    {
        int sum = 0;
        for (; index > 0; index -= index & -index)
            sum += binaryIndTree[index];
        return sum;
    }
    static void getQueryOutput(int[] arr, int n, Query[] queries, int q)
    {
        int[] binaryIndTree = new int[n + 1];
        Arrays.fill(binaryIndTree, 0);

        int[] visitedArray = new int[MAX];
        Arrays.fill(visitedArray, -1);

        int[] output = new int[q];
        int counter = 0;
        for (int i = 0; i < n; i++)
        {
            if (visitedArray[arr[i]] != -1)
                update(visitedArray[arr[i]] + 1, -1, binaryIndTree, n);

            visitedArray[arr[i]] = i;
            update(i + 1, 1, binaryIndTree, n);

            while (counter < q && queries[counter].r == i)
            {
                output[queries[counter].index] = query(queries[counter].r + 1, binaryIndTree, n) - query(queries[counter].l, binaryIndTree, n);
                counter++;
            }
        }
        for (int i = 0; i < q; i++)
            System.out.println(output[i]);
    }
    public static void main(String[] args)
    {
        int a[] = { 2,3,4,1,1};
        int n = a.length;
        Query[] queries = new Query[3];
        for (int i = 0; i < 3; i++)
            queries[i] = new Query();
        queries[0].l = 0;
        queries[0].r = 4;
        queries[0].index = 0;
        queries[1].l = 1;
        queries[1].r = 3;
        queries[1].index = 1;
        queries[2].l = 2;
        queries[2].r = 4;
        queries[2].index = 2;
        int q = queries.length;
        Arrays.sort(queries, new Comparator<Query>()
        {
            public int compare(Query x, Query y)
            {
                if (x.r < y.r)
                    return -1;
                else if (x.r == y.r)
                    return 0;
                else
                    return 1;
            }
        });
        getQueryOutput(a, n, queries, q);
    }
}
4
3
2

子數組中不同元素數量查詢的複雜度分析

時間複雜度

O(查詢* log n) 哪裡 “ n” 是輸入數組的大小。

空間複雜度

O(N) 哪裡 “ n” 是數組中元素的數量。

參考文獻