ການສອບຖາມ ສຳ ລັບ ຈຳ ນວນອົງປະກອບທີ່ແຕກຕ່າງໃນ Subarray  


ລະດັບຄວາມຫຍຸ້ງຍາກ Hard
ຖາມເລື້ອຍໆໃນ Amazon ກູໂກ Microsoft Oracle Uber
Array Segment-Tree ຕົ້ນໄມ້

ພວກເຮົາໄດ້ມອບ array ຂອງເລກເຕັມແລະ ຈຳ ນວນການສອບຖາມແລະພວກເຮົາຕ້ອງຊອກຫາ ຈຳ ນວນຂອງສ່ວນປະກອບທີ່ແຕກຕ່າງກັນທີ່ພວກເຮົາມີຢູ່ໃນຂອບເຂດທີ່ ກຳ ນົດໄວ້, ການສອບຖາມປະກອບດ້ວຍສອງຕົວເລກຢູ່ເບື້ອງຊ້າຍແລະຂວາ, ນີ້ແມ່ນຂອບເຂດທີ່ ກຳ ນົດໄວ້, ເຊິ່ງຊ່ວງນີ້ພວກເຮົາຕ້ອງ ຊອກຫາ ຈຳ ນວນຂອງສ່ວນປະກອບທີ່ແຕກຕ່າງ.

ຍົກຕົວຢ່າງ  

ການປ້ອນຂໍ້ມູນ:

ຮອດ [] = {2,3,4,1,1}

0​, 4

1​, 3

2​, 4

ຜົນໄດ້ຮັບ:

+4 3 2

ຄໍາອະທິບາຍ:

ໃນການສອບຖາມຄັ້ງ ທຳ ອິດ, ຈຳ ນວນຕົວເລກທີ່ແຕກຕ່າງໃນ [0 … 4] ແມ່ນ 4 (4, 3, 2,1). ໃນການສອບຖາມຄັ້ງທີສອງ, ຈຳ ນວນຕົວຄູນທີ່ແຕກຕ່າງກັນໃນ a [1..3] ແມ່ນ 3 (4, 3,1). ໃນການສອບຖາມຄັ້ງທີສາມ, ຈຳ ນວນຕົວຄູນທີ່ແຕກຕ່າງໃນ a [2..4] ແມ່ນ 2 (1, 4).

ຊອກຫາ ຈຳ ນວນຂອງສ່ວນປະກອບທີ່ແຕກຕ່າງກັນທີ່ພວກເຮົາມີຢູ່ພາຍໃນຂອບເຂດທີ່ ກຳ ນົດໄວ້,Pin

ລະບົບວິເຄາະ  

  1. ເຮັດໃຫ້ແທັກວັດຖຸແລະຢູ່ກັບແຕ່ລະ ຕຳ ແໜ່ງ ໃຫ້ ໝາຍ ຄ່າຄືຊ້າຍ, ຂວາແລະດັດສະນີທີ່ກ່ຽວຂ້ອງກັບແຕ່ລະອັນ ຈຸດ​ປະ​ສົງ.
  2. ຈັດຮຽງແຖວສອບຖາມທີ່ກ່ຽວຂ້ອງກັບມູນຄ່າທີ່ຖືກຕ້ອງຕາມລະດັບ.
  3. ສ້າງ binaryIndTree ຂບວນ [].
  4. ເລີ່ມຕົ້ນຍ່າງຜ່ານແຖວທີ່ໃຫ້ແລະພ້ອມໆກັນ ຄຳ ຖາມທີ່ໃຫ້,
  5. ກວດເບິ່ງວ່າ VisArray [a [i]] ແມ່ນ -1 ຫລືບໍ່.
  6. ຖ້າບໍ່ຖືກຕ້ອງ, ປັບປຸງ binaryIndTree array ທີ່ມີຄ່າ -1 ຢູ່ທີ່ດັດຊະນີທີ່ເວັບໄຊທ໌ visitArray [a [i]].
  7. ຕັ້ງຄ່າ visitArray [a [i]] = ຂ້ອຍແລະອັບເດດ binaryIndTree array binaryIndTree array ທີ່ມີຄ່າ 1 ຢູ່ index i.
  8. ຕັ້ງກົງກັນຂ້າມກັບ 0, ແລະເລີ່ມຕົ້້ນທາງຂວາງຈົນກວ່າວຽກງານຕ້ານການນ້ອຍກວ່າບໍ່ມີການສອບຖາມແລະຍັງເຮັດໃຫ້ການສອບຖາມມີມູນຄ່າເທົ່າກັບ i.
  9. ສຳ ລັບດັດສະນີຂອງວັດຖຸແຕ່ລະແບບ, ການປັບປຸງດັດສະນີ ຄຳ ຖາມມູນຄ່າເປັນຄວາມແຕກຕ່າງຂອງ ຄຳ ຖາມ 'ມູນຄ່າທີ່ຖືກຕ້ອງແລະມູນຄ່າເບື້ອງຊ້າຍຂອງການສອບຖາມ.
  10. ພິມຜົນທັງ ໝົດ ສຳ ລັບແຕ່ລະ ຄຳ ຖາມທີ່ ກຳ ນົດ.
ເບິ່ງ
ຈັດແຈງແຖວ ໃໝ່ ທີ່ 'arr [j]' ກາຍເປັນ 'i' ຖ້າ 'arr [i]' ແມ່ນ 'j'

ຄໍາອະທິບາຍ  

ພວກເຮົາ ກຳ ລັງຈະສ້າງແຖວຂອງວັດຖຸດັ່ງກ່າວກັບແຖວແຖວວັດຖຸນັ້ນພວກເຮົາຈະເຊື່ອມຕໍ່ເບື້ອງຊ້າຍ, ຂວາແລະດັດສະນີຫລື ຈຳ ນວນການສອບຖາມ. ຈາກນັ້ນພວກເຮົາຈະຈັດຮຽງຂໍ້ມູນແບບສອບຖາມດັ່ງກ່າວເຊິ່ງການສອບຖາມຈັດຮຽງຕາມ ລຳ ດັບຕັ້ງຂອງ 'ຄ່າ' ທີ່ຖືກຕ້ອງ, ໝາຍ ຄວາມວ່າ ຄຳ ຖາມທີ່ມີມູນຄ່າ ໜ້ອຍ ທີ່ສຸດຂອງ 'ສິດ' ຈະມາກ່ອນເປັນ ລຳ ດັບ.

ໃນປັດຈຸບັນ, ສ້າງຂບວນຊຶ່ງເປັນ binaryIndTree. ເລີ່ມຕົ້ນຄ່າທັງ ໝົດ ຂອງອາເລກັບ 0, ຫຼັງຈາກນັ້ນສ້າງຂະ ໜາດ ຂອງ max ຂະ ໜາດ, ເຊິ່ງເປັນ 1000001. ເລີ່ມຄ່າທຸກຄ່າຂອງ array ນີ້ໃຫ້ເປັນ -1 ແລະແຖວສຸດທ້າຍຂອງຜົນຂອງການຊອກຫາຂະ ໜາດ, ເພາະວ່າມັນຈະມີ ຈຳ ນວນດຽວກັນຂອງ ຜົນຜະລິດເປັນ ຈຳ ນວນຂອງການສອບຖາມ. ມູນຄ່າຂອງເຄື່ອງນັບຄວນຈະຖືກຕັ້ງຄ່າເປັນ 0. ດຽວນີ້ພວກເຮົາເລີ່ມຕົ້ນການເດີນທາງແຖວແລະກວດເບິ່ງວ່າເວັບໄຊທ໌ VisArray [arr [i]] = -1, ຖ້າພົບວ່າມັນເປັນຄວາມຈິງແລ້ວຄວນປັບປຸງຄ່າຂອງ binaryIndTree ກັບຄ່າ -1. ຫຼັງຈາກການປັບປຸງມູນຄ່າທີ່ visitArray [arr [i]] ກັບຂ້ອຍ, ແລະອີກເທື່ອ ໜຶ່ງ ປັບປຸງ binaryIndTree ກັບຄ່າ 1, ນີ້ແມ່ນໃຫ້ເຮັດບໍ່ວ່າເງື່ອນໄຂຂ້າງເທິງແມ່ນຖືກຫຼືບໍ່.

ພາຍໃນວົງຈອນນີ້, ເລີ່ມຕົ້ນປັບປຸງອາເລແລະນີ້ຕ້ອງເຮັດຈົນກ່ວາມູນຄ່າຂອງການເຄົາເຕີ້ແມ່ນຫນ້ອຍກ່ວາມູນຄ່າຂອງຕົວເລກຂອງການສອບຖາມ, q. ປັບປຸງແຖວຂອງຜົນຜະລິດດ້ວຍຄວາມແຕກຕ່າງຂອງມູນຄ່າເບື້ອງຂວາແລະແບບສອບຖາມ 'ມູນຄ່າເບື້ອງຊ້າຍແລະການປັບປຸງໃນແຕ່ລະດັດນີ, ຈື່ເວລາທີ່ພວກເຮົາສ້າງດັດສະນີໃຫ້ເທົ່າກັບ ຈຳ ນວນການສອບຖາມ. ແລະເພີ່ມມູນຄ່າຂອງວຽກງານຕ້ານການ. ສຸດທ້າຍ, ພິມຄ່າທັງ ໝົດ ໃນແຖວຜົນຜະລິດ.

ເບິ່ງ
ເລກດີໃຈ

ການປະຕິບັດ  

ໂປຣແກຣມ C ++ ສຳ ລັບ ຄຳ ຖາມ ສຳ ລັບ ຈຳ ນວນອົງປະກອບທີ່ແຕກຕ່າງໃນ Subarray

#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 ສຳ ລັບ ຄຳ ຖາມ ສຳ ລັບ ຈຳ ນວນອົງປະກອບທີ່ແຕກຕ່າງໃນ Subarray

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

ການວິເຄາະຄວາມສັບສົນ ສຳ ລັບການສອບຖາມ ສຳ ລັບ ຈຳ ນວນອົງປະກອບທີ່ແຕກຕ່າງໃນ Subarray  

ຄວາມສັບສົນເວລາ

O (ການສອບຖາມ * log n) ບ່ອນທີ່ "n" ແມ່ນຂະ ໜາດ ຂອງຂບວນການປ້ອນຂໍ້ມູນ.

ເບິ່ງ
String Matching in Array Leetcode Solution

ຄວາມສັບສົນໃນອະວະກາດ

O (n) ບ່ອນທີ່ "n" ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບໃນແຖວ.

ກະສານອ້າງອີງ