資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學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尋找解決方案的方法
樸素方法
解決這個問題的簡單方法是遍歷陣列到查詢索引，並檢查每個元素；如果它是 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;
// loop for running each query.
for(int i = 0;i<qsize;i++){
//counting zeros and ones
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。
另一種方法是首先計算每個索引左側存在的零和一，將它們儲存在一個數組中，並根據查詢中寫入的索引返回答案。
示例
#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;
// traverse through the nums array.
for (int i = 0; i < n; i++) {
// store the number of zeros and ones in arr.
arr[i][0] = zeros;
arr[i][1] = ones;
// increment variable according to condition
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 等程式語言來實現。希望本教程對您有所幫助。
更新於：2021年11月26日
161 次瀏覽
廣告