KK's blog

LeetCode 349 Intersection of Two Arrays

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].

Note:

• Each element in the result must be unique.
• The result can be in any order.

题目大意：

给定两个数组，编写函数计算它们的交集。

注意：
结果中的每个元素一定是唯一的。
结果可以采用任意顺序。

解题思路：

将较小的数组的所有元素放入hashSet，然后遍历另一个数组判断是否相同，相同的话放入hashSet的结果集中。所以需要两个hashSet。

Python代码：

1
2

def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
    return list(set(nums1) & set(nums2))

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public int[] intersection(int[] nums1, int[] nums2) {
	//swap and make sure length of nums1 is smaller
	if(nums1.length>nums2.length){
		int[] tmp = nums1;
		nums1 = nums2;
		nums2 = tmp;
	}
	
	Set<Integer> hash=new HashSet();
	Set<Integer> result=new HashSet();
	for(int i=0;i<nums1.length;i++)
		hash.add(nums1[i]);
	
	for(int i=0; i<nums2.length;i++){
		if(hash.contains(nums2[i]))
			result.add(nums2[i]);
	}
	int[] r=new int[result.size()];
	int k=0;
	for(int i : result)
		r[k++]=i;
	return r;       
}

算法分析：

m和n为数组长度m>n，时间复杂度为O(m)，空间复杂度O(n)。

LeetCode 350 Intersection of Two Arrays II

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2, 2].

Note:

• Each element in the result should appear as many times as it shows in both arrays.
• The result can be in any order.

Follow up:

• What if the given array is already sorted? How would you optimize your algorithm?
• What if nums1‘s size is small compared to nums2‘s size? Which algorithm is better?
• What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

题目大意：

给定两个数组，编写函数计算它们的交集。

注意：
结果中的每个元素的出现次数应与其在两个数组中同时出现的次数一样多。 结果可以采用任意顺序。

进一步思考：
如果数组已经排好序，怎样优化你的算法？
如果nums1的长度＜nums2的长度？哪一种算法更好？
如果nums2的元素存储在磁盘上，并且内存大小有限，不足以将其一次性的加载到内存中。此时应当怎样做？

解题思路：

类似于L349，但由于可允许重复，所以改hashSet成hashMap记录频数。具体而言，将较小的数组的所有元素放入hashMap且统计频数，
然后遍历另一个数组判断是否相同，相同的话放入ArrayList的结果集中且频数减一。

Python代码：

1
2
3
4
5
6
7
8

def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
	num_to_count = collections.Counter(nums1)
	res = []
	for n in nums2:
		if n in num_to_count and num_to_count[n] > 0:
			num_to_count[n] -= 1
			res.append(n)
	return res

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

public int[] intersect(int[] nums1, int[] nums2) {
	//swap and make sure length of nums1 is smaller
	if(nums1.length>nums2.length){
		int[] tmp = nums1;
		nums1 = nums2;
		nums2 = tmp;
	}
	
	Map<Integer, Integer> map=new HashMap<Integer, Integer>();
	List<Integer> result=new ArrayList();
	for(int i=0;i<nums1.length;i++){
		if(map.containsKey(nums1[i]))
			map.put(nums1[i], map.get(nums1[i])+1);
		else
			map.put(nums1[i],1);
	}
	
	for(int i=0; i<nums2.length;i++){
		if(map.containsKey(nums2[i]) && map.get(nums2[i])>0){
			result.add(nums2[i]);
			map.put(nums2[i], map.get(nums2[i])-1);
		}
	}
	return result.stream().mapToInt(i->i).toArray();      
}

算法分析：

m和n为数组长度m>n，时间复杂度为O(m)，空间复杂度O(n)。

算法II解题思路：

另一个解题思路是，先对它们排序，然后类似于mergeSort算法维持两个指针分别在两个数组搜索相同元素。

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

public int[] intersect(int[] nums1, int[] nums2) {
	List<Integer> result=new ArrayList();
	Arrays.sort(nums1);
	Arrays.sort(nums2);
	int i=0, j=0;
	while(i<nums1.length && j<nums2.length){
		if(nums1[i]==nums2[j]){
			result.add(nums1[i]);
			i++;
			j++;
		}
		else if(nums1[i]<nums2[j])
			i++;
		else j++;
	}
	return result.stream().mapToInt(k->k).toArray();
}

算法分析：

m和n为数组长度m>n，时间复杂度为O(mlogm)，空间复杂度O(1)。此算法空间较优，但时间稍逊。

1. 如果数组已经排好序，怎样优化你的算法？
   用第二个算法，时间复杂度为O(m),但空间复杂度可以优化为O(1)
2. 如果nums1的长度＜nums2的长度？哪一种算法更好？
   方法一更优，因为nums1空间用的比较少情况下
3. 如果nums2的元素存储在磁盘上，并且内存大小有限，不足以将其一次性的加载到内存中。此时应当怎样做？
   也应该用方法一，因为它不需要把nums2数组一次性加载到内存中。假设内存大小为L，每次L大小的内存可解决
   部分问题，时间复杂度为O(m),然后有n/L次，最后结果为O(mn)，表示空间有限时候，hashSet的方法不比先排序快。

第三种方法是一个数组排序，另一个可以不排序。不排序数组的每个元素在排序数组中用二分法查找。

LeetCode

Input
[“MovingAverage”, “next”, “next”, “next”, “next”]
[[3], [1], [10], [3], [5]]
Output
[null, 1.0, 5.5, 4.66667, 6.0]

Explanation
MovingAverage movingAverage = new MovingAverage(3);
movingAverage.next(1); // return 1.0 = 1 / 1
movingAverage.next(10); // return 5.5 = (1 + 10) / 2
movingAverage.next(3); // return 4.66667 = (1 + 10 + 3) / 3
movingAverage.next(5); // return 6.0 = (10 + 3 + 5) / 3

题目大意：

求data stream特定窗口的平均数

解题思路：

结构上跟LRU cache类似

解题步骤：

N/A

注意事项：

1. 用queue

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

def __init__(self, size: int):
	self.queue = collections.deque()
	self.size = size
	self.sum = 0

def next(self, val: int) -> float:
	if len(self.queue) < self.size:
		self.queue.append(val)
		self.sum += val
	else:
		n = self.queue.popleft()
		self.sum -= n
		self.queue.append(val)
		self.sum += val
	return self.sum / len(self.queue)

算法分析：

next时间复杂度为O(1)，空间复杂度O(n)

LeetCode

Input: s = “eceba”, k = 2
Output: 3
Explanation: The substring is “ece” with length 3.

Input: s = “aa”, k = 1
Output: 2
Explanation: The substring is “aa” with length 2.

题目大意：

求最长子串，它含有最多k种字符

解题思路：

同向双指针，属于最长串类型

解题步骤：

N/A

注意事项：

1. while条件中，反计算char_to_count，还要pop key

Python代码：

1
2
3
4
5
6
7
8
9
10
11

def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
	char_to_count, left, max_len = collections.defaultdict(int), 0, 0
	for i, char in enumerate(s):
		char_to_count[char] += 1
		while len(char_to_count) > k:
			char_to_count[s[left]] -= 1
			if char_to_count[s[left]] == 0:
				char_to_count.pop(s[left])
			left += 1
		max_len = max(max_len, i - left + 1)
	return max_len

算法分析：

时间复杂度为O(n)，空间复杂度O(k)

算法思路：

left is left pointer, i is right pointer
外循环为扩张，内循环为收缩。收缩条件为固定字符种数(必须固定或者少于k)或者(以及)固定字符频数。若字符种数不固定，要试1-26种字符，才能单调，详见L395

求最短串

Python代码：

1
2
3
4
5
6
7
8

def two_pointers(self, nums):
	for i in range(len(nums)):
		<calculate condition such as char_to_count>
		while <meets condition>:
			res = min(res, i - left + 1) <求最短子列>
			<anti-calculate condition such as char_to_count>
			left += 1
	return <result>

求最长串

Python代码：

1
2
3
4
5
6
7
8

def two_pointers(self, nums):
	for i in range(len(nums)):
		<calculate condition such as char_to_count>
		while <does not meet condition>:
			<anti-calculate condition such as char_to_count>
			left += 1
		res = max(res, i - left + 1) <求最短子列>
	return <result>

算法分析：

时间复杂度为O(n)，空间复杂度O(1)。