C++ 查询回答给定索引左侧的 1 和 0 的数量
c++server side programmingprogramming
讨论回答给定数组查询的问题。例如，对于每个查询索引，我们需要找到索引左侧的 1 和 0 的数量。
输入:arr[ ] = { 0, 1, 1, 1, 0, 0, 0, 1, 0, 0}, queries[ ] = { 2, 4, 1, 0, 5 }
输出:
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
输入:arr[ ] = { 0, 0, 1, 1, 1, 0, 1, 0, 0, 1 }, queries[ ] = { 3, 2, 6 }
输出:
query 1:zeros = 2,ones = 1
query 2:zeros = 2,ones = 0
query 3:zeros = 3,ones = 3
寻找解决方案的方法
简单方法
此问题的简单解决方案是遍历数组到查询的索引并检查每个元素；如果为 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
高效方法
在之前的方法中，我们每次都从第 0 个索引开始计算新查询的 1 和 0。
另一种方法是首先计算每个索引左侧的 0 和 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 n = sizeof(nums) / sizeof(nums[0]);
int arr[n][2];
int zeros = 0, others = 0;
// 遍历 nums 数组。
for (int i = 0; i < n; i++) {
// 将零和一的数量存储在 arr 中。
arr[i][0] = zeros;
arr[i][1] = others;
// 根据条件增加变量
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
结论
在本教程中，我们讨论了返回给定数组中每个查询的索引左侧的 1 和 0 的数量。我们讨论了解决此问题的简单方法和有效方法。我们还讨论了此问题的 C++ 程序，我们可以使用 C、Java、Python 等编程语言来完成。我们希望您觉得本教程有用。
