数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究C++ 中包含的重复项 II
假设我们有一个数组和一个整数 k，我们必须检查数组中是否具有两个不同的索引 i 和 j 使得 nums[i] = nums[j] 且 i 和 j 的绝对差值不超过 k。
因此，如果输入类似于 [1,2,4,1]且 k = 3，那么输出将为 True
为了解决此问题，我们将按照以下步骤进行操作 −
定义一个 pair 数组 nn
对 i := 0 初始化，当 i − num 大小时，更新（增加 i 1），执行 −
在 nn 的末尾插入 {nums[i], i}
对 nn 数组进行排序
对 i := 1 初始化，当 i < nn 大小时，更新（增加 i 1），执行 −
如果 nn[i] 的第一个元素与 nn[i - 1] 的第一个元素相同且 |nn[i] 的第二个元素 - nn[i - 1] 的第二个元素|，则 −
返回 true
返回 false
范例
让我们看看下面的实现以获得更好的理解 −
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
vector<pair<int, int> > nn;
for (<) {
nn.push_back(make_pair(nums[i], i));
}
sort(nn.begin(), nn.end());
for (int i = 1; i < nn.size(); i++) {
if (nn[i].first == nn[i - 1].first and abs(nn[i].second - nn[i - 1].second) <= k)
return true;
}
return false;
}
};
main(){
Solution ob;
vector<int> v = {1,2,4,1};
cout << (ob.containsNearbyDuplicate(v, 3));
}输入
{1,2,4,1}输出
1
更新于： 2020-6-10
174 查看
广告