ການສອບຖາມ ສຳ ລັບນັບຂອງອົງປະກອບ array ທີ່ມີຄ່າໃນຂອບເຂດທີ່ ກຳ ນົດໄວ້


ລະດັບຄວາມຫຍຸ້ງຍາກ Hard
ຖາມເລື້ອຍໆໃນ Coursera DE Shaw ກູໂກ PayU Snapdeal ອິນເຕີເນັດ Times Times Yahoo
Array ບິດ ບັນຫາການສອບຖາມ

ຖະແຫຼງການບັນຫາ

ບັນຫາ“ ການສອບຖາມ ສຳ ລັບນັບຂອງອົງປະກອບອາເລທີ່ມີຄ່າຢູ່ໃນຂອບເຂດ” ກ່າວວ່າທ່ານມີ integer array ແລະສອງຕົວເລກ x ແລະ y. ຄຳ ຖະແຫຼງກ່ຽວກັບບັນຫາຂໍໃຫ້ຊອກຫາການນັບ ຈຳ ນວນຂອງຕົວເລກທີ່ມີຢູ່ໃນແຖວທີ່ຢູ່ລະຫວ່າງຕົວເລກ x ແລະ y.

ຍົກຕົວຢ່າງ

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

ຄໍາອະທິບາຍ

ເນື່ອງຈາກວ່າມັນມີ 4 ອົງປະກອບທີ່ມີຢູ່ໃນອາເລ, ນັ້ນແມ່ນ 2, 4, 6, ແລະ 8 ທີ່ຢູ່ລະຫວ່າງ 2 ແລະ 8, ລວມ.

ການສອບຖາມ ສຳ ລັບນັບຂອງອົງປະກອບ array ທີ່ມີຄ່າໃນຂອບເຂດທີ່ ກຳ ນົດໄວ້

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

ຄໍາອະທິບາຍ

ເນື່ອງຈາກວ່າມີ 3 ອົງປະກອບທີ່ ນຳ ສະ ເໜີ ໃນອາເລ, ນັ້ນແມ່ນ 6, 8, ແລະ 10, ນັ້ນແມ່ນຢູ່ລະຫວ່າງ 5 ແລະ 10 ລວມ.

ລະບົບວິເຄາະ

  1. ການຈັດລຽງ ຂບວນການ.
  2. ຊອກຫາດັດສະນີຫຼາຍກວ່າເກົ່າຂອງອາເລຂອງອົງປະກອບ y ໂດຍໃຊ້ການຄົ້ນຫາຖານສອງ, ໃຫ້ດັດສະນີທີ່ສູງກວ່າ.
  3. ຊອກຫາດັດຊະນີທີ່ນ້ອຍກວ່າຂອງອາເລຂອງອົງປະກອບ x ໂດຍໃຊ້ການຄົ້ນຫາຖານສອງ, ສົ່ງຄືນດັດຊະນີທີ່ນ້ອຍກວ່າ.
  4. ສົ່ງຄືນຄວາມແຕກຕ່າງລະຫວ່າງດັດຊະນີທີ່ໃຫຍ່ກວ່າແລະດັດຊະນີທີ່ນ້ອຍກວ່າແລະບວກ 1.

ຄໍາອະທິບາຍ

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

ໄດ້ຮັບການດັດສະນີຂອງຈໍານວນ y ໃນແຖວໂດຍໃຊ້ການຄົ້ນຫາຖານສອງ. ໃນການຄົ້ນຫາຖານສອງ, ພວກເຮົາພະຍາຍາມຊອກຫາດັດສະນີທີ່ y ຢູ່. ພວກເຮົາສືບຕໍ່ໃນວົງຈອນຈົນກ່ວາມູນຄ່າຂອງຕ່ໍາແມ່ນຫນ້ອຍກ່ວາຫຼືເທົ່າກັບມູນຄ່າຂອງສູງ. ໂດຍປົກກະຕິແລ້ວຕ່ ຳ ແມ່ນດັດຊະນີ 0 ແລະສູງແມ່ນດັດຊະນີສຸດທ້າຍຂອງອາເລເພາະວ່າພວກເຮົາ ກຳ ລັງເຮັດການຄົ້ນຫາຖານສອງກ່ຽວກັບຕົວຊີ້ວັດຂອງແຖວ. ການ ນຳ ໃຊ້ການຄົ້ນຫາຖານສອງຊ່ວຍໃຫ້ພວກເຮົາ ti ຕອບ ຄຳ ຖາມ ສຳ ລັບການນັບ ຈຳ ນວນຂອງອົງປະກອບ array ທີ່ມີຄ່າໃນຂອບເຂດທີ່ມີຄວາມສັບສົນໃນ logarithmic time ສຳ ລັບແຕ່ລະ ຄຳ ຖາມ.

ພວກເຮົາຈະໄດ້ຮັບລະດັບກາງຂອງມູນຄ່າຕ່ ຳ ແລະສູງ, ແລະກວດເບິ່ງວ່າປັດໃຈທີ່ມີຢູ່ໃນອາເລ [ກາງ] ແມ່ນໃຫຍ່ກວ່າເທົ່າກັບ x. ຖ້າວ່ານີ້ແມ່ນຄວາມຈິງ, ຫຼັງຈາກນັ້ນປັບປຸງມູນຄ່າຂອງສູງເຖິງກາງ 1. ອື່ນປັບປຸງຄຸນຄ່າຂອງຕ່ ຳ ເຖິງກາງ +1. ຄືກັນກັບການ ນຳ ໃຊ້ກັບອົງປະກອບ y. ແຕ່ໃນກໍລະນີດັ່ງກ່າວ, ພວກເຮົາຈະຊອກຫາດັດສະນີທີ່ສູງກວ່າ, ແລະແທນທີ່ຈະກວດສອບແຖວ [ກາງ] ແມ່ນໃຫຍ່ກວ່າເທົ່າກັບ y. ຈາກນັ້ນໃຫ້ກວດກາເບິ່ງຖ້າອາເລ [ກາງ] ໜ້ອຍ ກວ່າ y, ແລະປັບປຸງຄ່າຂອງຕ່ ຳ ຫາກາງ + 1 ແລະມູນຄ່າຂອງສູງເຖິງກາງ 1.

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

ລະຫັດ

ລະຫັດ C ++ ເພື່ອຊອກຫາການນັບ ຈຳ ນວນຂອງອົງປະກອບ array ພາຍໃນຂອບເຂດໃດ ໜຶ່ງ

#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 ເພື່ອຊອກຫາການນັບ ຈຳ ນວນຂອງອົງປະກອບ array ພາຍໃນຂອບເຂດໃດ ໜຶ່ງ

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 (log n) ແລະ ສຳ ລັບການຈັດຮຽງແຖວຄັ້ງດຽວຈະເປັນ O (n log n).

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

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