Leetcode No.219( Contains Duplicate II) 心得
題目:
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;
}
};