Leetcode No.219( Contains Duplicate II) 心得

ChingYuanYang
Aug 24, 2017 · 3 min read

題目:

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k

想法:
第一個想法的確就是暴力法,畢竟每個數都要比對一次,好像沒有太多想法。然後就在最後一個test case超時了。
這時候就回想起之前用過 hash map,hash map對於檢查重複有很快的速度。
這部分對於 hash map 進一步了解,友分為 unordered_map 和 ordered_map,unordered_map就是 hash table,ordered_map是用search tree實作,搜尋速度比較慢。因此這邊用 unordered_map。

一開始作法是遇到重複的值,檢查index距離是不是在k內,後來參考網路上解法,可以改進為當 unordered_map裡面超過 k 個值,就移除最前面的值,因為新加入的值和第一個值的index差距一定超過 k。
這個作法有提升速度,減少陣列太大的記憶體問題,以及 duplicate發生什麼操作判斷。

class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
int size = nums.size();

unordered_map<int, int> map;
for (int i = 0; i < nums.size(); i++) {
if (i > k)
map.erase(nums[i — k — 1]);
bool ok = map.insert({ nums[i], i }).second;
if (ok == false)
return true;
}
return false;
}
};

網路上的作法:
這題有官方solution但是要付費會員才可以看…。
參考別人的方法,有一個更簡單的方式是用 unordered_set,unordered_set和 unordered_map 幾乎一樣,差別只在於 set 沒有 key 和 value,只有 value,但是 set 一樣有機制可以判別這個 insert 有沒有 duplicate。
set沒辦法記錄 index,這裡用的方法就是超過 k 個值的時候就移除最前面的值,也就是一值檢察 k 個範圍內有沒有重複的,有就回傳 true。

class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k)
{
unordered_set<int> s;

if (k <= 0) return false;
if (k >= nums.size()) k = nums.size() - 1;

for (int i = 0; i < nums.size(); i++)
{
if (i > k) s.erase(nums[i - k - 1]);
if (s.find(nums[i]) != s.end()) return true;
s.insert(nums[i]);
}

return false;
}
};
)
Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade