資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會學
時尚學
法學範圍求和查詢——不可變的 C++
假設我們有一個整數陣列。我們必須找到從索引 i 到 j 中的元素之和。我們需要記住兩件事：一是陣列不可變，因此不會更改元素；二是此類查詢會有很多。因此，我們必須考慮大量查詢的執行時間。假設陣列類似於 A = [5, 8, 3, 6, 1, 2, 5]，則如果查詢為 (A, 0, 3)，則其結果應為 5 + 8 + 3 + 6 = 22。
為了解決此問題，我們將按照以下步驟操作：
- 選擇一個數組 B。B[i] 將儲存從 0 到 i 的元素之和。
- 對於查詢，執行 B[j] – B[i – 1]
讓我們瞭解以下實施，以更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class NumArray {
public:
vector <int> pre;
NumArray(vector<int>& nums) {
pre.clear();
int n = nums.size();
pre.resize(n);
for(int i = 0; i < n; i++){
if(i == 0)pre[0] = nums[0];
else
pre[i] = pre[i - 1] + nums[i];
}
}
int sumRange(int i, int j) {
if(i == 0)return pre[j];
return pre[j] - pre[i - 1];
}
};
main(){
vector<int> v = {5,8,3,6,1,2,5};
NumArray na(v);
cout<<na.sumRange(0,2)<<endl;
cout<<na.sumRange(2,5)<<endl;
cout<<na.sumRange(0,5)<<endl;
}輸入
Initialize it with [5,8,3,6,1,2,5] Call sumRange(0,2) sumRange(2,5) sumRange(0,5)
輸出
16 12 25
更新於： 2020-4-28
118 次瀏覽
廣告