KK's blog

LeetCode 347 Top K Frequent Elements

Given a non-empty array of integers, return the k most frequent elements.

For example,
Given [1,1,1,2,2,3] and k = 2, return [1,2].

Note:

• You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
• Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.

题目大意：

给定一个非空整数数组，返回其前k个出现次数最多的元素。

注意：
你可以假设k总是有效的，1 ≤ k ≤ 独立元素的个数。
你的算法时间复杂度必须优于O(n log n)，其中n是数组的长度。

解题思路：

这是经典题，解法是HeapSelect：求最大k个数，就先对前k个元素建最小堆，然后遍历k到最后一个数，若它大于栈顶就替换且做minHeapify。最后结果是
最大的k个数在数组的前k个位置且堆顶（数组第一个数）为k个数的最小。堆并没有排序。
结果并不需要从大到小输出。

1. 统计词频
2. 建key-value数组
3. heapSelect
4. 把数组前k个数加入到结果集中

注意事项：

1. 如果需要按大到小输出结果，需要对result进行排序O(klogk)，数组第一个也就是最小堆堆顶是这k个数中最小。
2. key-pair版堆选择算法。

Python代码：

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

from heapq import heapreplace, heappush

def topKFrequent(self, nums: List[int], k: int) -> List[int]:
	dict = {}
	for i in range(len(nums)):
		if nums[i] not in dict:
			dict[nums[i]] = 1
		else:
			dict[nums[i]] += 1

	freq_dict = [(v, k) for k, v in dict.items()]
	res = []
	for i in range(len(freq_dict)):
		if i < k:
			heappush(res, freq_dict[i])
		elif freq_dict[i][0] > res[0][0]:
			heapreplace(res, freq_dict[i])

	return [v for k, v in res]

统计词频部分可以用Counter优化。freq_dict有两个作用：将key和频率互换，还可以将dict转换成list方便和k比较

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

from heapq import heapreplace, heappush
from collections import Counter

def topKFrequent(self, nums: List[int], k: int) -> List[int]:
	dict = Counter(nums)
	freq_dict = [(v, k) for k, v in dict.items()]
	res = []
	for i in range(len(freq_dict)):
		if i < k:
			heappush(res, freq_dict[i])
		elif freq_dict[i][0] > res[0][0]:
			heapreplace(res, freq_dict[i])

	return [v for k, v in 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

public List<Integer> topKFrequent(int[] nums, int k) {
	List<Integer> result = new ArrayList<Integer>();
	HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
	for(int i=0;i<nums.length;i++){
		if(map.containsKey(nums[i]))
			map.put(nums[i], map.get(nums[i])+1);
		else
			map.put(nums[i], 1);
	}
	Node[] f = new Node[map.size()];
	Iterator it = map.entrySet().iterator();
	int j=0;
	while(it.hasNext()){
		Map.Entry pair = (Map.Entry)it.next();
		Node node = new Node((int)pair.getKey(), (int)pair.getValue());
		f[j++] = node;
	}
	hselect(f, k);
	for(int i=0;i<k;i++)
		result.add(f[i].key);
	return result;
}
  
public void hselect(Node a[], int k){
	// min heap with size=k
	for (int i = k / 2; i >= 0; i--) {
		minHeapify(a, i, k);
	}
	for (int i = k; i < a.length; i++) {
		if (a[i].value > a[0].value) {
			swap(a, i, 0);
			minHeapify(a, 0, k);
		}
	}
}

public void minHeapify(Node[] arr, int i, int n) {
	int smallest = i;
	int l = left(i);
	int r = l + 1;
	if (l < n && arr[l].key < arr[smallest].key)
		smallest = l;
	if (r < n && arr[r].key < arr[smallest].key)
		smallest = r;
	if (smallest != i) {
		swap(arr, i, smallest);
		minHeapify(arr, smallest, n);
	}
}

private int left(int i) {
	return 2 * i + 1;
}

private void swap(Node[] arr, int index1, int index2) {
	Node tmp = arr[index1];
	arr[index1] = arr[index2];
	arr[index2] = tmp;
}

class Node {
	int key;
	int value;
	public Node(int k, int v){
		key = k;
		value = v;
	}
	
	public String toString(){
		return "("+key+","+value+")";
	}
}

算法分析：

时间复杂度为O(nlogk)，空间复杂度O(1)。时间复杂度是O(n)+O(nlogk),空间复杂度为O(m)+O(1),m为不重复的元素个数(unique element)。

算法II解题思路：

此题关于数组频数，所以考虑用桶排序(bucket sort)

1. 统计词频（元素->频数）
2. 桶排序：n+1个桶（n为原数组大小），把元素放入频数对应的桶号（频数->元素），用List把这些元素串起来。
3. 逆序（从大到小）遍历不为空的桶，输入结果直至k个。
   与上面算法不同的是结果是从大到小输出。数据类型有两个HashMap存储元素对应的频数，而List数组List[]反过来存储频数对应的元素。

注意事项：

1. 桶排序要用List串联起元素，例如[1,2],k=2，频数为1的元素有两个，所以桶的内容应该是List。Python用[[] for _ in range(len(nums) + 1)]
2. 桶数量为原数组大小+1，例如一个元素[1], 它的频数为1，而频数为0是不会出现。
3. 逆序遍历所有桶，只要结果集个数为k，就停止循环。

Python代码：

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

from collections import Counter

def topKFrequent(self, nums: List[int], k: int) -> List[int]:
	di = Counter(nums)
	freq = [[] for _ in range(len(nums) + 1)]
	for key, val in di.items():
		freq[val].append(key)
	res = []
	for i in range(len(freq) - 1, 0, -1):
		for n in freq[i]:
			if k > 0:
				res.append(n)
				k -= 1
	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

public List<Integer> topKFrequent2(int[] nums, int k) {
	 List<Integer> result = new ArrayList<Integer>();
	 HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
	 for(int i=0;i<nums.length;i++){
		if(map.containsKey(nums[i]))
			map.put(nums[i], map.get(nums[i])+1);
		else
			map.put(nums[i], 1);
	 }
	 List<Integer>[] f = new List[nums.length+1];
	 Iterator it = map.entrySet().iterator();
	 while(it.hasNext()){
		 Map.Entry pair = (Map.Entry)it.next();
		 if(f[(int)pair.getValue()]==null)
			 f[(int)pair.getValue()] = new ArrayList();
		 f[(int)pair.getValue()].add((int)pair.getKey());
	 }
	 for(int i=f.length-1;i>0 && result.size()<k;i--)
		 if(f[i]!=null){
			 result.addAll(f[i]);
		 }
	 return result;
}

算法分析：

时间复杂度为O(n)，空间复杂度O(n)。时间复杂度是O(n)+O(n),空间复杂度为O(m)+O(n),m为不重复的元素个数(unique element)。

Follow-up:

1. 题目可以包装成：给定一个文档，返回其前k个出现次数最多的单词。
   Given a document, return the k most frequent words. Assume punctuation are removed.
   Given a non-empty array of strings, return the k most frequent elements.
2. 如果写出了桶排序，可以考虑假设机器memory有限，只够O(m)，不能一次性读出整个文档，也就是不能用桶排序，只能用堆选择。
3. 如果写出了堆选择，可以考虑k比较大，如果进一步提高时间复杂度，也就是只能O(n),符合这个要求就只有计数排序，基数排序和桶排序。

这是priorityQueue实现的Heap（对于基本数据类型默认是最小堆，但由于Node是自定义，必须实现Comparator），由于PQ需要额外空间，所以
较少用。

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

public List<Integer> topKFrequent3(int[] nums, int k) {
	 List<Integer> result = new ArrayList<Integer>();
	 HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
	 for(int i=0;i<nums.length;i++){
		if(map.containsKey(nums[i]))
			map.put(nums[i], map.get(nums[i])+1);
		else
			map.put(nums[i], 1);
	 }
	 Node[] f = new Node[map.size()];
	 Iterator it = map.entrySet().iterator();
	 int j=0;
	 while(it.hasNext()){
		Map.Entry pair = (Map.Entry)it.next();
		Node node = new Node((int)pair.getKey(), (int)pair.getValue());
		f[j++] = node;
	 }
	 
	 PriorityQueue<Node> minHeap = new PriorityQueue<Node>(k,
			new Comparator<Node>() {
				@Override
				public int compare(Node o1, Node o2) {
					return o1.value - o2.value;
				}
			}
	);

	for (int i = 0; i < f.length; i++) {
		if (i < k) {
			minHeap.offer(f[i]);
		} 
		else {
			Node minNode = minHeap.peek();
			if (f[i].value > minNode.value) {
				minHeap.poll();
				minHeap.offer(f[i]);
			}
		}
	}

	while(!minHeap.isEmpty())
		result.add(minHeap.poll().key);
	return result;
 }

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 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 316 Remove Duplicate Letters

Given a string which contains only lowercase letters, remove duplicate letters so that every letter appear once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

Example:

Given "bcabc"
Return "abc"

Given "cbacdcbc"
Return "acdb"

题目大意：

给定一个只包含小写字母的字符串，从中移除重复字母使得每个字母只出现一次。你必须确保结果的字典序最小。

解题思路：

这题是保持原顺序输出结果，所以考虑用递减栈(递增栈，从栈底递增，求最小即用递增，如求k个最大用最小堆一样)。先看例子bcabc->abc，a入栈倒逼
bc出栈，可解此题。因为既然bc在栈外还有，就可以出栈，保证第一个字母最小（题目要求）。再看cbacdcbc，acd时候b入栈，不能倒逼cd出栈
因为d是唯一一个，所以还要维护一个hashMap来记录每个字母的词频。所以入栈条件为准入栈元素小于栈顶元素且栈顶元素为最后一个（频数>0）。
hashMap作用有两个，第一个为统计词频，第二个为记录未入栈的字母的频数。
resultSet记录stack中所有唯一元素，用于判断是否需要入栈。这是难点，对于已在栈中的重复元素不需要再入栈，因为它在栈中的位置已经是目前
最小的位置，如果要出现更小的结果只能通过非栈内元素倒逼产生新结果。如acabc，第二个a不需要逼c出来，b可以做到这一点，a已在最小位置。

注意事项：

1. 已在栈内的重复元素不入栈，也不倒逼任何元素出栈，也就是直接忽略它，只要将其频数减一即可，表示已处理。比如abacb，第二个a不能倒逼b。用两个数据结构：set保证不重复加入到栈内，map保证外面还有元素可入栈
2. 进入循环后频数立刻减一，不要出列时候才做，参见BFS。
3. 出栈条件：栈不为空，准入栈元素小于栈顶元素，栈顶元素频数>0（表示栈外还有元素可以入栈）。

Python代码：

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

def removeDuplicateLetters(self, s: str) -> str:
	char_to_count = collections.Counter(s)
	stack, stack_set = [], set()
	for i in range(len(s)):
		char_to_count[s[i]] -= 1
		if s[i] in stack_set:
			continue
		while stack and s[i] < stack[-1] and char_to_count[stack[-1]] > 0:
			stack_set.remove(stack[-1])
			stack.pop()
		stack.append(s[i])
		stack_set.add(s[i])
	return ''.join(stack)

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
26
27
28
29
30
31
32
33
34

public String removeDuplicateLetters(String s) {
	Stack<Character> stack = new Stack<Character>();
	Map<Character, Integer> map = new HashMap<Character, Integer>();
	Set<Character> result = new HashSet<Character>();
	
	for(int i=0;i<s.length();i++){
		Character c = s.charAt(i);
		if(map.containsKey(c))
			map.put(c, map.get(c)+1);
		else
			map.put(c, 1);
	}
	
	for(int i=0;i<s.length();i++){
		Character c = s.charAt(i);
		map.put(c, map.get(c)-1);
		
		//Stack已经有c就不加入
		if(result.contains(c))
			continue;
		
		while(!stack.isEmpty() && c<stack.peek() && map.get(stack.peek())>0){
			result.remove(stack.peek());
			stack.pop();
		}
		stack.push(c);
		result.add(c);
	}
	
	StringBuilder sb = new StringBuilder();
	while(!stack.isEmpty())
		sb.append(stack.pop());
	return sb.reverse().toString();  	
}

算法分析：

所有元素入栈出栈最多一次，所以时间复杂度为O(n)，空间复杂度O(n)。

LeetCode 312 Burst Balloons

Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get nums[left] * nums[i] * nums[right] coins. Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent.

Find the maximum coins you can collect by bursting the balloons wisely.

Note:
(1) You may imagine nums[-1] = nums[n] = 1. They are not real therefore you can not burst them.
(2) 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

Example:

Given [3, 1, 5, 8]

Return 167

    nums = [3,1,5,8] --> [3,5,8] -->   [3,8]   -->  [8]  --> []
   coins =  3*1*5      +  3*5*8    +  1*3*8      + 1*8*1   = 167

题目大意：

给定n个气球，下标为0到n-1。每个气球上都标有一个数字，用数组nums表示。你被要求扎破所有气球。扎破第i个气球可以获得nums[left] × nums[i] × nums[right]枚硬币。这里left和right是与i相邻的下标。扎破气球以后，left和right就变成相邻的了。
寻找最优策略下可以获得的硬币数。

注意：
(1) 你可以假设nums[-1] = nums[n] = 1. 它们并非真实的因此不能扎破。
(2) 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

解题思路：

1. 此题遍历所有可能性，所以考虑用DP
2. 因为一个参数不足以描述问题，因为并不能固定nums左端或右端，所以考虑二元DP，左右边界为参数。DP流程一：定义函数f(i,j)为nums[i..j]之间的最大硬币数。
3. 下一步写递归式，由于这是二元DP，参考Floyd和矩阵链乘法算法，一遍要定义一个k，二分法得到两个子问题的解f(i,k)和f(k,j)，求解它们的关系是难点。先写几个例子培养下思路：
   2,3,4
   f([2,4])=2×3×4同时消去了3变成[2,4],再写一个
   2,3,4,5,6,7,8
   k=5, 数组变成[2,5,8]所以我们定义中忽略了一个重要事实，修改为f(i,j)为nums[i..j]之间的最大硬币数及其它们之间的元素已经消去。
   这样的话，关系就很明朗了，只要消去5就可以得到f([2,8])，k的定义要可以清晰了：最后一个消去的元素。
   f(i,j)=max{f(i,m)+ nums[i]×nums[m]×nums[j] +f(m,j)}, i<m<j，m为整数
4. 我们还要试试nums为单元素和双元素情况下是否适用。比如单元素5，根据题目意思首先前后补1
   1,5,1 -> f(1,5)+1×5×1+f(5,1)=5这是正确的因为f(x,y)默认为0.
   1,5,3,1, k=5, f(1,5)+1×5×1+f(5,1)=0+5+(5×3×1)=20 | k=3, f(1,3)+1×3×1+f(3,1)=(1×5×3)+3+0=18.所以也是正确，且f(x,y)默认为0没问题。

5. 遍历顺序。一开始我用i,j,m三重循环，但结果不对。主要因为这个计算过程与演算过程不一致，我们刚才的演算过程是先计算所有i和j之间的值。例如，
   1, 5, 3, 1
   i        j
   i            j
       i        j

   在第二次循环的时候f(i,j)已经计算出来很显然是不对的。

注意事项：

1. 二元DP([i,j],k的递归式)+二分法。 二元DP中k的引入参考Floyd按步长计算。nums[i] * nums[m] * nums[j]而不是nums[m-1] * nums[m] * nums[m+1]
2. 原数组前后补1，这样巧妙地让递归式适用于一个元素的情况，避免特别处理。因此步长可以k=2开始，i<m<j不取等号。dp数组以新数组为边界
3. 遍历顺序也类似于Floyd，先k(步长且至少为2)，再遍历矩阵i和j。特别注意i<n-k而不是i<n

Python代码：

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

def maxCoins(self, nums: List[int]) -> int:
	ary = list(nums)
	ary.insert(0, 1)
	ary.append(1)
	N = len(ary)
	dp = [[0 for _ in range(N)] for _ in range(N)]
	for k in range(2, N):
		for i in range(0, N - k):
			j = i + k
			for m in range(i + 1, j):
				dp[i][j] = max(dp[i][j], dp[i][m] + ary[i] * ary[m] * ary[j] + dp[m][j])
	return dp[0][N - 1]

Java代码：

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

public int maxCoins(int[] nums) {
	int n = nums.length+2;
	int[] coins = new int[n];
	
	for(int i=0;i<nums.length;i++)
		coins[i+1]=nums[i];
	coins[0] = coins[n-1] = 1;
	
	int[][] dp = new int[n][n];
	for(int k=2;k<n;k++)
		for(int i=0;i<n - k;i++){
			int j = i+k;
			for(int m=i+1;m<j;m++)
				dp[i][j] = Math.max(dp[i][j], dp[i][m]+coins[i]*coins[m]*coins[j] + dp[m][j]);
				
		}
	return dp[0][n-1];
}

算法分析：

三重循环，时间复杂度为O(n3)，空间复杂度O(n2)。