ในปัญหานี้ เราได้รับ arr[] และ Q เคียวรีแต่ละรายการประกอบด้วยค่า m งานของเราคือการสร้างโปรแกรมเพื่อแก้ปัญหาการสืบค้นสำหรับการนับทวีคูณในอาร์เรย์ใน C++
คำอธิบายปัญหา
ในการแก้โจทย์ เราต้องนับจำนวนทั้งหมดที่เป็นทวีคูณของ m สำหรับสิ่งนี้เราจะตรวจสอบองค์ประกอบที่หารด้วย m ได้
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ป้อนข้อมูล :arr[] ={4, 7, 3, 8, 12, 15}
Q =3 ข้อความค้นหา[] ={2, 3, 5}
เอาท์พุต :3 3 1
คำอธิบาย
แบบสอบถาม 1:m =2 ทวีคูณในอาร์เรย์ =4, 8, 12. นับ =3
แบบสอบถาม 2:m =3 ทวีคูณในอาร์เรย์ =3, 12, 15. นับ =3
แบบสอบถาม 3:m =5 ทวีคูณในอาร์เรย์ =15 นับ =1
แนวทางการแก้ปัญหา
วิธีแก้ไขอย่างง่ายคือการสำรวจอาร์เรย์สำหรับค่าการสืบค้นแต่ละรายการและนับจำนวนองค์ประกอบของอาร์เรย์ที่หารด้วย m ลงตัว
ตัวอย่าง
#include <iostream>
using namespace std;
int solveQuery(int arr[], int N, int m){
int count = 0;
for(int i = 0; i < N; i++){
if(arr[i]%m == 0)
count++;
}
return count;
}
int main(){
int arr[] = {4, 7, 3, 8, 12, 15};
int N = sizeof(arr)/sizeof(arr[0]);
int Q = 3;
int query[] = {2, 3, 5};
for(int i = 0; i < Q; i++)
cout<<"The count of multiples in array "<<solveQuery(arr, N,query[i])<<endl;
return 0;
} ผลลัพธ์
The count of multiples in array 3 The count of multiples in array 3 The count of multiples in array 1
โซลูชันนี้จะข้ามอาร์เรย์หนึ่งครั้งสำหรับทุกการสืบค้นที่ทำให้เวลาซับซ้อน O(Q*n)
ทางออกที่ดีกว่าคือการใช้ Sieve of Eratosthenes เพื่อค้นหาตัวคูณทั้งหมด
และองค์ประกอบนับสำหรับอาร์เรย์ที่กำหนด แนวคิดคือการคำนวณล่วงหน้าจำนวนทวีคูณขององค์ประกอบทั้งหมดไม่เกินค่าสูงสุดของอาร์เรย์ จากนั้นเรียกอาร์เรย์ที่คำนวณไว้ล่วงหน้าเพื่อค้นหาจำนวนทวีคูณสำหรับการสืบค้น
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
int preCalcCount[10001];
void PreCalculateMultiples(int arr[], int N){
int maxVal = *max_element(arr, arr + N);
int count[maxVal + 1];
memset(count, 0, sizeof(count));
memset(preCalcCount, 0, (maxVal + 1) * sizeof(int));
for (int i = 0; i < N; ++i)
++count[arr[i]];
for (int i = 1; i <= maxVal; ++i)
for (int j = i; j <= maxVal; j += i)
preCalcCount[i] += count[j];
}
int main(){
int arr[] = {4, 7, 3, 8, 12, 15};
int N = sizeof(arr)/sizeof(arr[0]);
int Q = 3;
int query[Q] = {2, 3, 5};
PreCalculateMultiples(arr, N);
for(int i = 0; i < Q; i++)
cout<<"The count of multiples in array"<<preCalcCount[query[i]]<<endl;
return 0;
} ผลลัพธ์
The count of multiples in array 3 The count of multiples in array 3 The count of multiples in array 1
