C++ คิวรีตอบจำนวน 1 และ 0 ด้านซ้ายของดัชนีที่กำหนด

อภิปรายปัญหาตอบคิวรีให้กับอาร์เรย์ที่กำหนด สำหรับดัชนีคิวรีแต่ละอัน เราต้องหาจำนวน 1 และ 0 ด้านซ้ายของดัชนี ตัวอย่างเช่น:

Input: arr[] = { 0, 1, 1, 1, 0, 0, 0, 1, 0, 0 }, queries[] = { 2, 4, 1, 0, 5 }
Output: query 1: zeros = 1, ones = 1
        query 2: zeros = 1, ones = 3
        query 3: zeros = 1, ones = 0
        query 4: zeros = 0, ones = 0
        query 5: zeros = 2, ones = 3

Input: arr[] = { 0, 0, 1, 1, 1, 0, 1, 0, 0, 1 }, queries[] = { 3, 2, 6 }
Output: query 1: zeros = 2, ones = 1
        query 2: zeros = 2, ones = 0
        query 3: zeros = 3, ones = 3

วิธีการหาคำตอบ

วิธี Naive (วิธีตรงไปตรงมา)

วิธีง่ายๆ ในการแก้ปัญหานี้คือ เดินทางผ่านอาร์เรย์ไปยังดัชนีของคิวรี และตรวจสอบแต่ละองค์ประกอบ ถ้าเป็น 0 เพิ่มตัวนับศูนย์ขึ้น 1 มิฉะนั้น เพิ่มตัวนับหนึ่งขึ้น 1

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;

int main(){
    int nums[] = {1, 0, 0, 1, 1, 0, 0, 1, 0, 0};
    int queries[] = { 2, 4, 1, 0, 5 };
    int qsize = sizeof(queries) / sizeof(queries[0]);
    int zeros=0, ones=0;
    // ลูปสำหรับรันแต่ละคิวรี
    for(int i = 0; i < qsize; i++){
        // นับศูนย์และหนึ่ง
        for(int j = 0; j < queries[i]; j++){
            if(nums[j]==0)
                zeros++;
            else
                ones++;
        }
        cout << "\nquery " << i+1 << ": zeros = " << zeros << ",ones = " << ones;
        zeros=0;
        ones=0;
    }
    return 0;
}

ผลลัพธ์

query 1: zeros = 1,ones = 1
query 2: zeros = 2,ones = 2
query 3: zeros = 0,ones = 1
query 4: zeros = 0,ones = 0
query 5: zeros = 2,ones = 3

วิธีที่มีประสิทธิภาพ (Efficient Approach)

ในวิธีก่อนหน้า ทุกครั้งเรากำลังคำนวณหนึ่งและศูนย์สำหรับคิวรีใหม่จากดัชนี 0

อีกวิธีหนึ่งคือ คำนวณศูนย์และหนึ่งที่อยู่ด้านซ้ายของทุกดัชนีก่อน เก็บไว้ในอาร์เรย์ และคืนคำตอบตามดัชนีที่เขียนในคิวรี

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;

int main(){
    int nums[] = {1, 0, 0, 1, 1, 0, 0, 1, 0, 0};
    int queries[] = { 2, 4, 1, 0, 5 };
    int n = sizeof(nums) / sizeof(nums[0]);
    int arr[n][2];
    int zeros = 0, ones = 0;
    // เดินทางผ่าน nums array
    for (int i = 0; i < n; i++) {
        // เก็บจำนวนศูนย์และหนึ่งใน arr
        arr[i][0] = zeros;
        arr[i][1] = ones;
        // เพิ่มตัวแปรตามเงื่อนไข
        if (nums[i]==0)
            zeros++;
        else
            ones++;
    }
    int qsize = sizeof(queries) / sizeof(queries[0]);
    for (int i = 0; i < qsize; i++)
        cout << "\nquery " << i+1 << ": zeros = " << arr[queries[i]][0] << ",ones =" << arr[queries[i]][1];
    return 0;
}

ผลลัพธ์

query 1: zeros = 1,ones = 1
query 2: zeros = 2,ones = 2
query 3: zeros = 0,ones = 1
query 4: zeros = 0,ones = 0
query 5: zeros = 2,ones = 3

สรุป

ในบทช่วยสอนนี้ เราอภิปรายการคืนค่าจำนวนหนึ่งและศูนย์ทางซ้ายของดัชนีสำหรับแต่ละคิวรีในอาร์เรย์ที่กำหนด เราอภิปรายวิธีง่ายๆ และวิธีที่มีประสิทธิภาพในการแก้ปัญหานี้ เรายังอภิปรายโปรแกรม C++ สำหรับปัญหานี้ซึ่งเราสามารถทำได้กับภาษาโปรแกรมมิ่งอย่าง C, Java, Python ฯลฯ เราหวังว่าบทช่วยสอนนี้จะเป็นประโยชน์