细语呢喃

技术改变生活

0%

leetcode Contains Duplicate 整理

发表于 分类于 ， 阅读次数： 评论数：

本次题解包括：

  • 217 Contains Duplicate
  • 219 Contains Duplicate II
  • 220 Contains Duplicate III

217. Contains Duplicate

Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

题目地址: leetcode Contains Duplicate

题意：给定一个数组，求它是否有重复的元素

思路：Hash

Python 

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
    def containsDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        vis = set()
        for num in nums:
            if num in vis: return True
            vis.add(num)
        return False

写成oneline也行

1
2
3
4
5
6
7
class Solution(object):
    def containsDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        return len(set(nums)) != len(nums)

C++ 

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
	bool containsDuplicate(vector<int>& nums) {
		unordered_set<int> set;
		for (int num : nums) {
			if (set.find(num) != set.end()) return true;
			set.insert(num);
		}
		return false;
	}
};

Java 

1
2
3
4
5
6
7
8
9
10
class Solution {
    public boolean containsDuplicate(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        for(int num:nums) {
            if(set.contains((num))) return true;
            set.add(num);
        }
        return false;
    }
}

 

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 difference between i and j is at most k.

题目地址: leetcode Contains Duplicate II

题意，给定一个数组和整数k，问数组中是否有i - j <=k 并且nums[i] == nums[j]的两个不同的下标

思路：同样的hash，记录下标即可

C++ 

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
	bool containsNearbyDuplicate(vector<int>& nums, int k) {
		unordered_map<int, int> hash;
		for (int i = 0; i < nums.size(); i++) {
			if (hash.find(nums[i]) != hash.end() && i - hash[nums[i]] <= k)
				return true;
			hash[nums[i]] = i;
		}
		return false;
	}
};

Java 

1
2
3
4
5
6
7
8
9
10
class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        HashMap<Integer, Integer> index = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (i - index.getOrDefault(nums[i], -k - 1) <= k) return true;
            index.put(nums[i], i);
        }
        return false;
    }
}

Python 

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def containsNearbyDuplicate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: bool
        """
        vis = {}
        for i, num in enumerate(nums):
            if num in vis and i - vis[num] <= k:
                return True
            vis[num] = i
        return False

 

220. Contains Duplicate III

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

题目地址: leetcode Contains Duplicate III

题意：给定一个数组和两个整数t 和k ，求是否有不同的两个下标i和j，满足nums[i] - nums[j]<= t && i - j <=k

思路：

方法1

平衡树的方法。复杂度O(nlogk)

题意有：-t <= x- nums[i] <= t

左边有 nums[i]  - t <= x 因此把符合条件的数构建成一颗平衡树，然后查找一个最小的x使得x>= nums[i] - t

如果该x还满足 x  <= t + nums[i]就是我们要的答案啦

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
typedef long long LL;
class Solution {
public:
	bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
		if (k <= 0 || t < 0) return false;
		set<LL> order;
		for (int i = 0; i < nums.size(); i++) {
			auto it = order.lower_bound((LL)nums[i] - (LL)t);
			if (it != order.end() && *it <= (LL)nums[i] + (LL)t)
				return true;
			if (i >= k) order.erase(nums[i - k]);
			order.insert(nums[i]);
		}
		return false;
	}
};

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if (k <= 0  t < 0) return false;
        TreeSet<Long> tree = new TreeSet<>();
        for (int i = 0; i < nums.length; i++) {
            Long x = tree.ceiling((long) nums[i] - t);
            if (x != null && x <= (long) nums[i] + t) return true;
            if (i >= k)
                tree.remove((long) nums[i - k]);
            tree.add((long) nums[i]);
        }
        return false;
    }
}

 

方法2

桶的方法 O(n)

思想是以t+1为间隔来分桶，对于一个数，将其分到第key = num / (t + 1) 个桶中，我们只需要查找相同的和相邻的桶的元素就可以判断有无重复。

比如t = 4，那么04为桶0，59为桶1，10~14为桶2 。

使用t+1个桶是为啥？这是为了避免除以0的错误，可能t = 0.

下面，C++和Java的版本，如果num为负数，那么key -= 1，因为比C++/Java 的负数取整是：-2 /3 = 0，这题这样是不行的。

而Python则OK, -2 // 3 = -1。

C++ 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
typedef long long LL;
class Solution {
public:
	bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
		if (k <= 0 || t < 0) return false;
		unordered_map<LL, LL> keyToVal;
		LL div = (LL) t + 1;
		for (int i = 0; i < nums.size(); i++) {
			LL num = (LL)nums[i];
			LL key = num / div;
            if(num < 0) key--;
			if (keyToVal.find(key) != keyToVal.end()
				|| keyToVal.find(key + 1) != keyToVal.end() && keyToVal[key + 1] - num <= t
				|| keyToVal.find(key - 1) != keyToVal.end() && num - keyToVal[key - 1] <= t)
				return true;
			if (i >= k) {
                LL key2 = (LL)nums[i - k] / div;
                keyToVal.erase(nums[i - k] < 0 ? key2 - 1 : key2);
            }
			keyToVal[key] = num;
		}
		return false;
	}
};

Java 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if(k <= 0  t < 0) return false;
        HashMap<Long, Long> keyToNum = new HashMap<>();
        long div = (long)t + 1;
        for (int i = 0; i < nums.length; i++) {
            long num = (long)nums[i];
            long key = num / div;
            if(num < 0) key--;
            if (keyToNum.containsKey(key)
                     keyToNum.containsKey(key + 1) && keyToNum.get(key + 1) - num <= t
                     keyToNum.containsKey(key - 1) && num - keyToNum.get(key - 1) <= t)
                return true;
            if (i >= k) {
                long key2 = ((long)nums[i - k]) / div;
                keyToNum.remove(nums[i - k] < 0 ? key2 - 1 : key2);
            }
            keyToNum.put(key, num);
        }
        return false;
    }
}

Python 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def containsNearbyAlmostDuplicate(self, nums, k, t):
        """
        :type nums: List[int]
        :type k: int
        :type t: int
        :rtype: bool
        """
        if k <= 0 or t < 0: return False
        key_to_val = {}
        for i, num in enumerate(nums):
            key = num // (t + 1)
            if key in key_to_val \
                    or key + 1 in key_to_val and key_to_val[key + 1] - num <= t \
                    or key - 1 in key_to_val and num - key_to_val[key - 1] <= t:
                return True
            if i >=k:
                del key_to_val[nums[i-k] // (t + 1)]
            key_to_val[key] = num
        return False

 

更多题解可以查看： https://www.hrwhisper.me/leetcode-algorithm-solution/

请我喝杯咖啡吧~