Sunday, March 27, 2016

LeetCode 219 - Contains Duplicate II

LeetCode 219 - Contains Duplicate II
LeetCode 217 - Contains Duplicate
LeetCode 220 - Contains Duplicate III
http://www.programcreek.com/2014/05/leetcode-contains-duplicate-ii-java/
Given an array of integers and an integer k, return true if and only if there are two distinct indices i and j in the array such that nums[i] = nums[j] and the difference between i and j is at most k.
X. Using Set and sliding window
public boolean containsNearbyDuplicate(int[] nums, int k) { HashSet<Integer> hs=new HashSet<>(); for(int i=0;i<nums.length;i++) { if(hs.add(nums[i])==false) return true; if(hs.size()==k+1) hs.remove(nums[i-k]); } return false; }
My set only contain the numbers in the window. slide the window which is size k, if the new coming number cannot be add to set then return true. The time complexity is O(n), space complexity is O(k).
public boolean containsNearbyDuplicate(int[] nums, int k) { HashSet<Integer> set = new HashSet<Integer>(); for(int i=0;i<nums.length && i<=k;i++){ if(!set.add(nums[i])){ return true; } } for(int i=k+1;i<nums.length;i++){ set.remove(nums[i-k-1]); if(!set.add(nums[i])){ return true; } } return false; }
public boolean containsNearbyDuplicate(int[] nums, int k) { Set<Integer> set = new HashSet<Integer>(); for(int i = 0; i < nums.length; i++){ if(i > k) set.remove(nums[i-k-1]); if(!set.add(nums[i])) return true; } return false; }
http://my.oschina.net/Tsybius2014/blog/517511
`    ``public` `boolean` `containsNearbyDuplicate(``int``[] nums, ``int` `k) {`
`        ``if` `(nums.length <= ``1``) {`
`            ``return` `false``;`
`        ``}`
`        ``HashSet<Integer> hashSet = ``new` `HashSet<Integer>();`
`        ``for` `(``int` `i = ``0``; i < nums.length; i++) {`
`            ``if` `(i > k) {`
`                ``hashSet.remove(nums[i - k - ``1``]);`
`            ``}`
`            ``if` `(!hashSet.add(nums[i])) {`
`                ``return` `true``;`
`            ``}`
`        ``}`
`        ``return` `false``;`
`    ``}`
X. Using HashMap
 ```public boolean containsNearbyDuplicate(int[] nums, int k) { HashMap map = new HashMap();   for(int i=0; i
Generally people forget that map.put() can return
public boolean containsNearbyDuplicate(int[] nums, int k) { Map<Integer, Integer> map = new HashMap<Integer, Integer>(); for(int i = 0; i < nums.length; i++) { Integer ord = map.put(nums[i], i); if(ord != null && i - ord <= k) { return true; } } return false; }
def containsNearbyDuplicate(self, nums, k): numDict = dict() for x in range(len(nums)): idx = numDict.get(nums[x]) if idx >= 0 and x - idx <= k: return True numDict[nums[x]] = x return False

 ```public boolean containsNearbyDuplicate(int[] nums, int k) { HashMap map = new HashMap(); int min = Integer.MAX_VALUE;   for(int i=0; i

Brute Force
`    ``public` `boolean` `containsNearbyDuplicate(``int``[] nums, ``int` `k) {`
`        `
`        ``if` `(nums.length <= ``1``) {`
`            ``return` `false``;`
`        ``}`
`        ``for` `(``int` `i = ``0``; i < nums.length; i++) {`
`            ``for` `(``int` `j = i + ``1``; j <= i + k && j < nums.length; j++) {`
`                ``if` `(nums[i] == nums[j]) {`
`                    ``return` `true``;`
`                ``}`
`            ``}`
`        ``}`
`        `
`        ``return` `false``;`
`    ``}`