数据结构
网络
关系数据库管理系统 (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 次浏览
广告