資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++ 中陣列中倍數計數的查詢
在這個問題中，我們給定一個 arr[] 和 Q 個查詢，每個查詢包含一個值 m。我們的任務是建立一個程式來解決 C++ 中陣列中倍數計數的查詢。
問題描述
為了解決這些查詢，我們需要計算所有 m 的倍數。為此，我們將檢查可被 m 整除的元素。
讓我們舉個例子來理解這個問題，
輸入:arr[] = {4, 7, 3, 8, 12, 15}
Q = 3 query[] = {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)。
一個更好的解決方案是使用埃拉托色尼篩法找到所有倍數
以及給定陣列的元素計數。其思想是預先計算陣列最大值之前所有元素的倍數計數。然後呼叫預先計算的陣列來查詢查詢的倍數計數。
示例
#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
更新於: 2020年10月9日
289 次檢視
廣告