แบบสอบถามสำหรับค่าทศนิยมของ Subarrays ของ Binary Array


ระดับความยาก กลาง
ถามบ่อยใน อเมซอน Google
แถว ปัญหาการสืบค้น

เขียนแบบสอบถามสำหรับค่าทศนิยมของ subarrays ของอาร์เรย์ไบนารีในอาร์เรย์ไบนารีที่กำหนด คำสั่งปัญหาขอให้ค้นหาเลขฐานสิบที่สร้างขึ้นด้วยความช่วยเหลือของช่วงในอาร์เรย์ไบนารี

ตัวอย่าง

Input:

arr [] = {1, 0, 1, 1, 0, 0, 1, 1}

แบบสอบถาม (1, 5)

แบบสอบถาม (3, 6)

Output:

12 9

คำอธิบาย:

ผลลัพธ์ที่เกิดขึ้นเป็นตัวเลขฐานสองที่แสดงอยู่ในช่วง 1 ถึง 5 รวม (01100) คือ 12

ผลลัพธ์จึงเกิดขึ้นเป็นไฟล์ เลขฐานสอง แสดงในช่วง 3 ถึง 6 รวม (1001) คือ 9

เคียวรีสำหรับค่าทศนิยมของ subarrays ของไบนารีอาร์เรย์

 

อัลกอริทึมสำหรับแบบสอบถามสำหรับค่าทศนิยมของ subarrays ของอาร์เรย์ไบนารี

  1. สร้างอาร์เรย์เป็น prefixArray เริ่มต้นด้วย 0
  2. คัดลอกองค์ประกอบสุดท้ายของ prefixArray ไปยังองค์ประกอบสุดท้ายของไฟล์ แถว ให้
  3. สำรวจอาร์เรย์จากขวาไปซ้ายของอาร์เรย์และจัดเก็บผลคูณขององค์ประกอบอาร์เรย์ที่กำหนดและกำลังของ 2 และเพิ่มด้วยคำนำหน้าอาร์เรย์
  4. รับแบบสอบถามหากค่าทางขวาไม่เท่ากับค่าดัชนีสุดท้ายของอาร์เรย์ที่กำหนดให้ส่งคืนการแบ่งส่วนความแตกต่างของ prefixArray [ซ้าย] และ prefixArray [right + 1] และการดำเนินการ shift ของ 1 และด้านขวา ดัชนีของอาร์เรย์
  5. ส่งกลับการแบ่งส่วนของคำนำหน้าอาร์เรย์ [ซ้าย] และการดำเนินการ shift ของ 1 และดัชนีด้านขวาของอาร์เรย์

คำอธิบายสำหรับแบบสอบถามสำหรับค่าทศนิยมของ subarrays ของอาร์เรย์ไบนารี

เกี่ยวกับปัญหาการสอบถามค่าทศนิยมของ subarrays ของอาร์เรย์ไบนารีให้ก อาร์เรย์ไบนารี และช่วงของดัชนีเป็นดัชนีด้านซ้ายและดัชนีด้านขวา ค้นหารูปแบบทศนิยมของเลขฐานสองที่กำหนดซึ่งสร้างขึ้นด้วยช่วงที่กำหนด เราจะได้รับคำถามที่เราได้ระบุช่วง เราต้องหาเลขฐานสิบที่เกิดจากเลขฐานสองที่มีช่วง สำหรับสิ่งนี้เราจะสร้างอาร์เรย์พิเศษที่มีขนาดเท่ากับความยาวของอาร์เรย์ เราจะสร้างอาร์เรย์นั้นหรือเราสามารถพูดได้ว่าเราสามารถประมวลผลอาร์เรย์นั้นล่วงหน้าและเติมค่าบางอย่างลงไปเพื่อที่เราจะได้แก้แบบสอบถามในเวลาคงที่

สำรวจอาร์เรย์ แต่ก่อนที่จะข้ามอาร์เรย์ให้เติมอาร์เรย์ด้วย 0 ใน java เมื่อสร้างอาร์เรย์นั้นจะเต็มไปด้วย 0 โดยอัตโนมัติ แต่ใน C ++ เราต้องทำด้วยตัวเอง หลังจากนั้นรับผลคูณขององค์ประกอบอาร์เรย์สุดท้ายและ 1 บันทึกค่าในองค์ประกอบสุดท้ายของ prefixArray ตอนนี้เริ่มจากขวาไปซ้ายหมายถึงเริ่มจาก 2nd องค์ประกอบสุดท้ายของอาร์เรย์ตอนนี้รับผลคูณของตัวเลขที่มีกำลัง 2 และองค์ประกอบอาร์เรย์ที่กำหนดและเพิ่มด้วยค่าก่อนหน้าของ prefixArray ให้เพิ่มด้วยค่าของ prefixArray และเก็บไว้ในตำแหน่งที่เกี่ยวข้องของ prefixArray

สำหรับแต่ละแบบสอบถามที่ให้กับเราตรวจสอบว่าค่าที่ถูกต้องไม่เท่ากับดัชนีสุดท้ายของอาร์เรย์หรือไม่ หากพบว่าเป็นจริงให้รับความแตกต่าง prefixArray [ซ้าย] และ prefixArray [ขวา] แล้วหารด้วยค่าที่เกิดขึ้นเมื่อเราใช้การดำเนินการ shift ในพาวเวอร์ของ 2 และส่งคืนค่านั้นมิฉะนั้นจะคืนค่าความแตกต่าง ของ prefixArray [ซ้าย] และหารด้วยการดำเนินการ shift ในค่าที่ถูกต้องและส่งคืน

การดำเนินงาน

โปรแกรม C ++

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

using namespace std;

void buildArray(int arr[], int n, int prefixArray[])
{
    memset(prefixArray, 0, n * sizeof(int));
    prefixArray[n - 1] = arr[n - 1] * pow(2, 0);
    for (int i = n - 2; i >= 0; i--)
        prefixArray[i] = prefixArray[i + 1] + arr[i] * (1 << (n - 1 - i));
}
int getDeimalNum(int arr[], int left, int right, int n, int prefixArray[])
{
    if (right!= n - 1)
        return (prefixArray[left] - prefixArray[right + 1]) / (1 << (n - 1 - right));

    return prefixArray[left] / (1 << (n - 1 - right));
}
int main()
{
    int arr[] = {1, 0, 1, 1, 0, 0, 1, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);

    int prefixArray[n];
    buildArray(arr, n, prefixArray);
    cout << getDeimalNum(arr, 1, 5, n, prefixArray) << endl;
    cout << getDeimalNum(arr, 3, 6, n, prefixArray) << endl;
    return 0;
}
12
9

โปรแกรม Java

import java.util.Arrays;

class DecimalfromSubArray
{
    static void buildArray(int arr[], int n, int prefixArray[])
    {
        Arrays.fill(prefixArray, 0);
        prefixArray[n - 1] = arr[n - 1] * (int)(Math.pow(2, 0));
        for (int i = n - 2; i >= 0; i--)
        {
            prefixArray[i] = prefixArray[i + 1] + arr[i] * (1 << (n - 1 - i));
        }
    }
    
    static int getDeimalNum(int arr[], int left, int right, int n, int prefixArray[])
    {
        if (right != n - 1)
        {
            return (prefixArray[left] - prefixArray[right + 1]) / (1 << (n - 1 - right));
        }
        return prefixArray[left] / (1 << (n - 1 - right));
    }
    
    public static void main(String[] args)
    {
        int arr[] = {1, 0, 1, 1, 0, 0, 1, 1};
        int n = arr.length;

        int prefixArray[] = new int[n];
        buildArray(arr, n, prefixArray);

        System.out.println(getDeimalNum(arr,1, 5, n, prefixArray));

        System.out.println(getDeimalNum(arr,3, 6, n, prefixArray));
    }
}
12
9

การวิเคราะห์ความซับซ้อนสำหรับแบบสอบถามสำหรับค่าทศนิยมของ Subarrays ของ Binary Array

ความซับซ้อนของเวลา

O (q) ที่ไหน "Q" คือจำนวนข้อความค้นหา

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

O (n) ที่ไหน “ n” คือจำนวนองค์ประกอบในอาร์เรย์

การอ้างอิง