資料結構
網路
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 檢視
廣告