แบบสอบถามสำหรับจำนวนองค์ประกอบอาร์เรย์ที่มีค่าในช่วงที่กำหนด  


ระดับความยาก ยาก
ถามบ่อยใน Coursera เดอชอว์ Google payu Snapdeal ไทม์อินเทอร์เน็ต yahoo
แถว เกร็ด ปัญหาการสืบค้น

คำชี้แจงปัญหา  

ปัญหา“ การสืบค้นจำนวนองค์ประกอบอาร์เรย์ที่มีค่าในช่วงที่กำหนด” ระบุว่าคุณมีไฟล์ จำนวนเต็ม แถว และเลขสองตัว x และ y คำสั่งปัญหาขอให้ค้นหาจำนวนตัวเลขที่มีอยู่ในอาร์เรย์ที่อยู่ระหว่าง x และ y ที่กำหนด

ตัวอย่าง  

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

คำอธิบาย

เนื่องจากมี 4 องค์ประกอบที่มีอยู่ในอาร์เรย์นั่นคือ 2, 4, 6 และ 8 ที่อยู่ระหว่าง 2 และ 8 โดยรวม

แบบสอบถามสำหรับจำนวนองค์ประกอบอาร์เรย์ที่มีค่าในช่วงที่กำหนดหมุด

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 อยู่ เราดำเนินการวนซ้ำจนกว่าค่าต่ำจะน้อยกว่าหรือเท่ากับค่าของสูง โดยปกติแล้ว low คือดัชนี 0 และ high คือดัชนีสุดท้ายของอาร์เรย์เนื่องจากเราทำการค้นหาไบนารีบนดัชนีอาร์เรย์ การใช้การค้นหาแบบไบนารีช่วยให้เราสามารถตอบแบบสอบถามจำนวนองค์ประกอบอาร์เรย์ที่มีค่าในช่วงที่กำหนดในความซับซ้อนของเวลาลอการิทึมสำหรับแต่ละแบบสอบถาม

เราจะได้ค่ากลางของค่าต่ำและค่าสูงและตรวจสอบว่าองค์ประกอบที่อยู่ในอาร์เรย์ [กลาง] มากกว่าเท่ากับ x หรือไม่ หากเป็นจริงให้อัปเดตค่าสูงเป็นกลาง -1 อื่นอัปเดตค่าต่ำถึงกลาง + 1 เช่นเดียวกับที่จะนำไปใช้กับองค์ประกอบ y แต่ในกรณีนี้เราจะพบดัชนีที่มากกว่าและแทนที่จะตรวจสอบอาร์เรย์ [กลาง] มากกว่าเท่ากับ y จากนั้นตรวจสอบว่าอาร์เรย์ [กลาง] น้อยกว่าเท่ากับ y หรือไม่และอัปเดตค่าต่ำเป็นกลาง + 1 และค่าสูงเป็นกลาง -1

รับดัชนีทั้งสองเป็นค่ามากกว่าและเล็กแล้วส่งกลับผลต่างของดัชนีแล้วบวก 1 เข้าไป นี่จะเป็นคำตอบที่เราต้องการซึ่งส่งคืนมา โปรดจำไว้ว่าเราต้องการตอบคำถามสำหรับจำนวนองค์ประกอบอาร์เรย์ที่มีค่าในช่วงที่กำหนด

รหัส  

รหัส C ++ เพื่อค้นหาจำนวนองค์ประกอบอาร์เรย์ภายในช่วงที่กำหนด

#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 เพื่อค้นหาจำนวนองค์ประกอบอาร์เรย์ภายในช่วงที่กำหนด

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 (บันทึก n) และสำหรับการจัดเรียงอาร์เรย์ครั้งเดียวจะเป็น O (n บันทึก n).

ดูสิ่งนี้ด้วย
จะตรวจสอบได้อย่างไรว่าสองชุดที่กำหนดไม่ปะติดปะต่อกัน?

ความซับซ้อนของอวกาศ

O (n) ที่ไหน “ n” คือจำนวนองค์ประกอบในอาร์เรย์ ช่องว่างที่เราได้พิจารณาเป็นเพราะช่องว่างที่นำมาระหว่างการเรียงลำดับอาร์เรย์ พื้นที่ที่จำเป็นสำหรับการจัดเก็บอินพุตจะไม่ได้รับการพิจารณาในปัญหา "การสืบค้นสำหรับจำนวนองค์ประกอบอาร์เรย์ที่มีค่าในช่วงที่กำหนด"