資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++陣列中的K-差對
假設我們有一個數組和一個整數k，我們需要找到陣列中唯一k-差對的數量。這裡的k-差對是指(i, j)這樣的對，其中i和j都存在於陣列中，並且它們的絕對差為k。
因此，如果輸入是[3,1,4,1,5]，k = 2，則輸出為2，因為陣列中有兩個2-差對：(1,3)和(3,5)。
為了解決這個問題，我們將遵循以下步驟：
定義名為seen和done的對映
定義一個集合s
如果k < 0，則：
返回0
對於初始化i := 0，當i < nums的大小，更新 (i增加1)，執行：
(seen[nums[i]]增加1)
將nums[i]插入s
ans := 0
對於集合s中的每個元素it，執行：
如果k等於0，則：
如果seen[it] > 1，則：
(ans增加1)
否則
done[it]增加1
如果(it + k)在seen中但不在done中，則：
(ans增加1)
如果(it - k)在seen中但不在done中，則：
(ans增加1)
返回ans
示例
讓我們看看下面的實現，以便更好地理解：
#include <bits/stdc++.h&g;
using namespace std;
class Solution {
public:
int findPairs(vector<int>& nums, int k) {
map<int, int> seen, done;
set<int> s;
if (k < 0)
return 0;
for (int i = 0; i < nums.size(); i++) {
seen[nums[i]]++;
s.insert(nums[i]);
}
int ans = 0;
for (auto it = s.begin(); it != s.end(); it++) {
if (k == 0) {
if (seen[*it] > 1)
ans++;
}
else {
done[*it]++;
if (seen.find(*it + k) != seen.end() && done.find(*it + k) == done.end())
ans++;
if (seen.find(*it - k) != seen.end() && done.find(*it - k) == done.end())
ans++;
}
}
return ans;
}
};
main(){
Solution ob;
vector<int> v = {3,1,4,1,5};
cout << (ob.findPairs(v, 2));
}輸入
{3,1,4,1,5}, 2輸出
2
更新於：2020年6月10日
304 次瀏覽
廣告