ການສອບຖາມຂັ້ນຕ່ ຳ ສຸດ (ການເນົ່າເປື່ອຍຮາກຮຽບຮ້ອຍແລະຕາຕະລາງກະແຈກກະຈາຍ)


ລະດັບຄວາມຫຍຸ້ງຍາກ Hard
ຖາມເລື້ອຍໆໃນ Amazon ຈາກຫນາກແອບເປີ ກູໂກ
Array Segment-Tree

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

ຍົກຕົວຢ່າງ

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

ມາຮອດ [] = {2, 5, 8, 6, 13, 9, 7, 10}

ການສອບຖາມ = {(0, 5), (1, 4), (3, 7)}

ຜົນໄດ້ຮັບ:

+2 5 6

ຄໍາອະທິບາຍ:

2 ແມ່ນ ຈຳ ນວນ ຕຳ ່ສຸດໃນ ຈຳ ນວນຊ່ວງ {2, 5, 8, 6, 13, 9}

5 ອັນຕ່ ຳ ສຸດໃນ ຈຳ ນວນຊ່ວງ {5, 8, 6, 13}

6 ແມ່ນຕ່ ຳ ສຸດໃນ ຈຳ ນວນຊ່ວງ {6, 13, 9, 7, 10}

ການສອບຖາມຂັ້ນຕ່ ຳ ສຸດ (ການເນົ່າເປື່ອຍຮາກຮຽບຮ້ອຍແລະຕາຕະລາງກະແຈກກະຈາຍ)

ລະບົບວິເຄາະ

  1. ສ້າງແຖວ 2D ແລະສ້າງມັນ. ສຳ ລັບສິ່ງນັ້ນ, ໃຫ້ ໝາຍ 0th ຖັນຂອງທຸກໆແຖວເປັນຄ່າຂອງດັດຊະນີແຖວຂອງມັນ.
  2. ລອກແຖວອາເລ, ແລະກວດເບິ່ງວ່າອາເລຂອງແຖວຊອກຫາທີ່ i, j-1 ແມ່ນຫນ້ອຍກ່ວາແຖວຂອງການຊອກຫາແຖວທີ່ i + 2j-1, j-1, ຖ້າຖືກຕ້ອງແລ້ວປັບປຸງການຊອກຫາທີ່ i, j ເປັນແຖວຊອກຫາທີ່ i, j-1.
  3. ປັບປຸງແບບອື່ນທີ່ຊອກຫາຢູ່ທີ່ i, j ເປັນການຊອກຫາຂບວນທີ່ i + 2j-1, j-1
  4. ສຳ ລັບການສອບຖາມແຕ່ລະອັນ, ໃຫ້ມີຂອບເຂດເບື້ອງຊ້າຍແລະເບື້ອງຂວາຂອງ ຄຳ ຖາມ, ໄດ້ຮັບຄ່າ log ຂອງເບື້ອງຂວາ + 1 ແລະກວດເບິ່ງວ່າ array ຂອງການຊອກຫາຢູ່ເບື້ອງຊ້າຍ, j ແມ່ນ ໜ້ອຍ ກ່ວາເທົ່າກັບອາເລຂອງການຊອກຫາຢູ່ເບື້ອງຂວາ - 2j +1, j, ຫຼັງຈາກນັ້ນສົ່ງຄືນຄ່າດັ່ງກ່າວເປັນແຖວຂອງການຊອກຫາຢູ່ເບື້ອງຂວາ - 2j + 1, ຈ.
  5. ພິມມູນຄ່າທີ່ສົ່ງຄືນ

ຄຳ ອະທິບາຍ ສຳ ລັບການສອບຖາມຂັ້ນຕ່ ຳ ສຸດ Range (ການເນົ່າເປື່ອຍຂອງຮາກຮຽບຮ້ອຍແລະໂຕະກະແຈກກະຈາຍ)

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

ພວກເຮົາຈະສ້າງຕາຕະລາງຊອກຫາ, ເພາະວ່າພວກເຮົາຈະ ນຳ ໃຊ້ອາຄານຊອກຫາ. ໃນການກໍ່ສ້າງ loop ຂຶ້ນແຖວ, ສຳ ລັບການຊອກຫາແຕ່ລະຄັ້ງທີ່ i, j ຖື ຕຳ ່ສຸດຂອງຄ່າຕ່າງໆຕັ້ງແຕ່ i ເຖິງ 2J. ແຖວຊອກຫາທີ່ i, j ຈະຖືດັດສະນີຂອງຄ່າຕ່າງໆຕາມແຕ່ລະຄ່າຂອງອາເລ. ໃນຂະນະທີ່ ກຳ ລັງຂ້າມຜ່ານອາເລ, ພວກເຮົາຈະ ກຳ ນົດມູນຄ່າ ຕຳ ່ສຸດ ສຳ ລັບຊ່ວງໃດ ໜຶ່ງ ຂອງຂະ ໜາດ ທີ່ເປັນໄປໄດ້ດັ່ງທີ່ 2 ຍົກຂຶ້ນມາເປັນ ກຳ ລັງ j ຍ້ອນເຫດຜົນດັ່ງກ່າວ, ພວກເຮົາຈະສາມາດຊອກຫາມູນຄ່າທີ່ເປັນໄປໄດ້ໃນຂອບເຂດທີ່ ກຳ ນົດໄວ້.

ສຳ ລັບການສອບຖາມລະດັບໃດ ໜຶ່ງ, ພວກເຮົາຈະ ນຳ ໃຊ້ຂອບເຂດຄືກັບ ອຳ ນາດຂອງ 2. ພວກເຮົາຈະ ນຳ ໃຊ້ຄ່າຂອງລະດັບຕ່າງໆເພື່ອຊອກຫາ log ຂອງຄວາມແຕກຕ່າງຂອງເບື້ອງຂວາ + 1 ແລ້ວພວກເຮົາຈະປຽບທຽບອາເລຂອງການຊອກຫາຢູ່ເບື້ອງຊ້າຍ, j ແມ່ນນ້ອຍກ່ວາຂີດຂວາຂອງ - 2j + 1, j, ຖ້າສະພາບການພົບວ່າຖືກຕ້ອງ, ຈາກນັ້ນໃຫ້ສົ່ງມູນຄ່າຂອງອາເລທີ່ຊອກຫາຢູ່ເບື້ອງຊ້າຍ, j, ອີກອັນ ໜຶ່ງ ສົ່ງຄືນອາເລທີ່ຊອກຫາຢູ່ເບື້ອງຂວາ - 2j + 1, ຈ. ນີ້ຈະເປັນ ຄຳ ຕອບທີ່ ຈຳ ເປັນ.

ການປະຕິບັດ

ໂປແກຼມ C ++ ສຳ ລັບການສອບຖາມແບບ Range Minimum Query (ການເສື່ອມສະພາບຮາກ Square ແລະໂຕະກະແຈກກະຈາຍ)

#include<iostream>
#include<math.h>

using namespace std;

#define MAX 500

int lookup[MAX][MAX];

struct Query
{
    int Left, Right;
};

void buildLookup(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        lookup[i][0] = i;
    for (int j=1; (1<<j)<=n; j++)
    {
        for (int i=0; (i+(1<<j)-1) < n; i++)
        {
            if (arr[lookup[i][j-1]] < arr[lookup[i + (1<<(j-1))][j-1]])
                lookup[i][j] = lookup[i][j-1];
            else
                lookup[i][j] = lookup[i + (1 << (j-1))][j-1];
        }
    }
}

int solveQuery(int arr[], int Left, int Right)
{
    int j = (int)log2(Right - Left + 1);

    if (arr[lookup[Left][j]] <= arr[lookup[Right - (1 << j) + 1][j]])
        return arr[lookup[Left][j]];

    else return arr[lookup[Right - (1<<j) + 1][j]];
}

void getMinimumNumber(int arr[], int n, Query q[], int m)
{
    for (int i = 0; i < m; i++)
    {
        int Left = q[i].Left, Right = q[i].Right;
        cout <<"Minimum value between ["<<Left<<", "<<Right<<"] is:"<< solveQuery(arr, Left, Right) << endl;
    }
}

int main()
{
    int a[] = {2,5,8,6,13,9,7,10};
    int n = sizeof(a)/sizeof(a[0]);
    Query q[] = {{0, 5}, {1, 4}, {3, 7}};
    int m = sizeof(q)/sizeof(q[0]);

    buildLookup(a, n);
    getMinimumNumber(a, n, q, m);
    return 0;
}
Minimum value between [0, 5] is:2
Minimum value between [1, 4] is:5
Minimum value between [3, 7] is:6

ໂຄງການ Java ສຳ ລັບການສອບຖາມແບບ Range Minimum Query (Square Decomposition Square ແລະ Sparse Table)

class MinimumNumberQuery
{
    static int MAX = 500;

    static int [][]lookup = new int[MAX][MAX];

    static class Query
    {
        int Left, Right;

        public Query(int Left, int Right)
        {
            this.Left = Left;
            this.Right = Right;
        }
    }
    
    static void	buildLookup(int arr[], int n)
    {
        for (int i = 0; i < n; i++)
            lookup[i][0] = i;

        for (int j = 1; (1 << j) <= n; j++)
        {
            for (int i = 0; (i + (1 << j) - 1) < n; i++)
            {
                if (arr[lookup[i][j - 1]] < arr[lookup[i + (1 << (j - 1))][j - 1]])
                    lookup[i][j] = lookup[i][j - 1];
                else
                    lookup[i][j] = lookup[i + (1 << (j - 1))][j - 1];
            }
        }
    }
    
    static int solveQuery(int arr[], int Left, int Right)
    {
        int j = (int)Math.log(Right - Left + 1);

        if (arr[lookup[Left][j]] <= arr[lookup[Right - (1 << j) + 1][j]])
            return arr[lookup[Left][j]];

        else return arr[lookup[Right - (1<<j) + 1][j]];
    }
    
    static void getMinimumNumber(int arr[], int n, Query q[], int m)
    {
        for (int i = 0; i < m; i++)
        {
            int Left = q[i].Left, Right = q[i].Right;

            System.out.println("Minimum of [" + Left + ", " + Right +
                               "] is " + solveQuery(arr, Left, Right));
        }
    }
    
    public static void main(String[] args)
    {
        int arr[] = {2,5,8,6,13,9,7,10};
        int n = arr.length;
        Query q[] = {new Query(0, 5),
                  new Query(1, 4),
                  new Query(3, 7)
        };
        int m = q.length;

        buildLookup(arr, n);
        getMinimumNumber(arr, n, q, m);
    }
}
Minimum of [0, 5] is 2
Minimum of [1, 4] is 5
Minimum of [3, 7] is 6

ການວິເຄາະຄວາມສັບສົນ ສຳ ລັບ

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

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

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

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

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