資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告