資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++程式：查詢陣列中滿足給定條件的數對個數
假設我們有一個包含n個數字的陣列nums。我們必須從陣列中選擇一對數字，並且有一個條件是它們在陣列中的位置差等於這兩個數字之和。從給定的數字陣列中，最多可以有n(n - 1)/2個可能的數對。我們必須找出陣列中滿足此條件的數對的總數。
因此，如果輸入為n = 8，nums = {4, 2, 1, 0, 1, 2, 3, 3}，則輸出為13。
陣列中可能有13個這樣的數對。
為了解決這個問題，我們將遵循以下步驟：
Define an array vals(n) for initialize i := 0, when i < n, update (increase i by 1), do: vals[i] := i + 1 - nums[i] sort the array vals res := 0 for initialize i := 0, when i < n, update (increase i by 1), do: k := nums[i] + i + 1 res := res + (position of first occurrence of a value not less than k in array vals - position of first occurrence of a value not greater than k in array vals) return res
示例
讓我們看下面的實現來更好地理解：
#include <bits/stdc++.h>
using namespace std;
int solve(int n, vector<int> nums){
vector<int> vals(n);
for( int i = 0; i < n; i++)
vals[i] = i + 1 - nums[i];
sort(vals.begin(), vals.end());
int res = 0;
for( int i = 0; i < n; i++ ) {
int k = nums[i] + i + 1;
res += upper_bound(vals.begin(), vals.end(), k) - lower_bound(vals.begin(), vals.end(), k);
}
return res;
}
int main() {
int n = 8;
vector<int> nums = {4, 2, 1, 0, 1, 2, 3, 3};
cout<< solve(n, nums);
return 0;
}輸入
8, {4, 2, 1, 0, 1, 2, 3, 3}
輸出
13
更新於：2022年3月2日
2K+ 次瀏覽
廣告