LeetCode 第 217 題：存在重復元素
傳送門：217. 存在重復元素。
給定一個整數(shù)數(shù)組，判斷是否存在重復元素。
如果任何值在數(shù)組中出現(xiàn)至少兩次，函數(shù)返回 true。如果數(shù)組中每個元素都不相同，則返回 false。
示例 1:
輸入: [1,2,3,1] 輸出: true示例 2:
輸入: [1,2,3,4] 輸出: false示例 3:
輸入: [1,1,1,3,3,4,3,2,4,2] 輸出: true
思路1：使用哈希表。
Python 代碼：
class Solution:
def containsDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
s = set()
for num in nums:
if num in s:
return True
else:
s.add(num)
return False
if __name__ == '__main__':
nums = [0]
s = Solution()
result = s.containsDuplicate(nums)
print(result)
思路2：排序以后再判斷重復。
Python 代碼：
class Solution:
def containsDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
if len(nums) < 2:
return False
# 原地排序
nums.sort()
for index in range(1, len(nums)):
if nums[index] == nums[index - 1]:
return True
return False
LeetCode 第 219 題：存在重復元素 II
傳送門：219. 存在重復元素 II。
給定一個整數(shù)數(shù)組和一個整數(shù) k，判斷數(shù)組中是否存在兩個不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的絕對值最大為 k。
示例 1:
輸入: nums = [1,2,3,1], k = 3 輸出: true示例 2:
輸入: nums = [1,0,1,1], k = 1 輸出: true示例 3:
輸入: nums = [1,2,3,1,2,3], k = 2 輸出: false
Python 代碼：
class Solution:
# 應該寫 is not None
# 判斷存在重復元素的索引之差小于某個數(shù)
def containsNearbyDuplicate(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: bool
"""
# 給定一個整數(shù)數(shù)組和一個整數(shù) k，
# 判斷數(shù)組中是否存在兩個不同的索引 i 和 j，
# 使得 nums [i] = nums [j]，
# 并且 i 和 j 的差的絕對值最大為 k。
# 先判斷 nums [i] = nums [j]
# 然后判斷索引值是否相等，所以索引值可以用 map 存起來。
size = len(nums)
if size == 0:
return False
map = dict()
for index in range(size):
if nums[index] in map and index - map[nums[index]] <= k:
# 只要存在就返回了，
return True
# 更新為最新的索引
map[nums[index]] = index
return False
LeetCode 第 220 題：存在重復元素 III
傳送門：220. 存在重復元素 III。
給定一個整數(shù)數(shù)組，判斷數(shù)組中是否有兩個不同的索引 i 和 j，使得 nums [i] 和 nums [j] 的差的絕對值最大為 t，并且 i 和 j 之間的差的絕對值最大為 ?。
示例 1:
輸入: nums = [1,2,3,1], k = 3, t = 0 輸出: true示例 2:
輸入: nums = [1,0,1,1], k = 1, t = 2 輸出: true示例 3:
輸入: nums = [1,5,9,1,5,9], k = 2, t = 3 輸出: false
Java 代碼：滑動窗口 + 查找表，這里的查找表是能查詢上界和下界的 BST。
class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
int len = nums.length;
if (len == 0 || k <= 0 || t < 0) {
return false;
}
TreeSet<Integer> treeSet = new TreeSet<>();
for (int i = 0; i < len; i++) {
// 大于等于 nums[i] 的最小數(shù)
Integer ceiling = treeSet.ceiling(nums[i]);
if (ceiling != null && (long) ceiling - (long) nums[i] <= t) {
return true;
}
// 小于等于 nums[i] 的最大數(shù)
Integer floor = treeSet.floor(nums[i]);
if (floor != null && (long) nums[i] - (long) floor <= t) {
return true;
}
treeSet.add(nums[i]);
if (i >= k) {
treeSet.remove(nums[i - k]);
}
}
return false;
}
}
參考資料：
1、https://blog.csdn.net/qq_20141867/article/details/82024222
使用有序字典。
2、Python 代碼，使用自己實現(xiàn)的 BST：https://leetcode.com/problems/contains-duplicate-iii/discuss/174416/Python-balanced-BST-solution
（本節(jié)完）
