数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学检查给定数组中是否存在 C++ 中彼此 k 距离内的重复元素
我们将学习如何检查未排序数组中是否存在彼此 k 距离内的重复元素。假设元素列表为 {1, 2, 3, 1, 4, 5}，如果 k = 3，则程序将返回 true，因为两个 1 之间的距离为 3。
我们将使用哈希表来解决这个问题。步骤如下：
- 创建一个空的哈希表
- 对于每个索引 i，令列表中的元素 e = arr[i]，执行以下操作：
- 如果 e 存在于哈希表中，则返回 true
- 否则，将 e 添加到哈希表中，并在 i >= K 时，如果存在，则从哈希表中删除第 (i-k) 个元素。
示例
#include<iostream>
#include<set>
using namespace std;
bool hasDuplicateWithDistK(int arr[], int n, int k) {
set<int> element_set;
for (int i = 0; i < n; i++) {
if (element_set.find(arr[i]) != element_set.end())
return true;
element_set.insert(arr[i]);
if (i >= k)
element_set.erase(arr[i-k]);
}
return false;
}
int main () {
int arr[] = {10, 5, 3, 4, 3, 5, 6};
int n = sizeof(arr) / sizeof(arr[0]);
if (hasDuplicateWithDistK(arr, n, 3))
cout << "Duplicate element has found";
else
cout << "Duplicate element has not found";
}输出
Duplicate element has found
更新于：2019年10月22日
371 次浏览
广告