查询子数组中不同元素的数量


难度级别
经常问 亚马逊 谷歌 微软 神谕 尤伯杯
排列 段树

我们给了 排列 整数和多个查询,我们必须找出给定范围内所有不同元素的数量,查询由左右两个数字组成,这是给定范围,必须在给定范围内找出不同元素的数量。

使用案列

输入:

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

0,4

1,3

2,4

输出:

4

说明:

在第一个查询中,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” 是数组中元素的数量。

参考