KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode 126 Word Ladder



Given two words (beginWord and endWord), and a dictionary’s word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:

1. Only one letter can be changed at a time
2. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

Note:

Return an empty list if there is no such transformation sequence. All words have the same length.
All words contain only lowercase alphabetic characters. You may assume no duplicates in the word list.
You may assume beginWord and endWord are non-empty and are not the same.

Example 1:

Input:
beginWord = “hit”,
endWord = “cog”,
wordList = [“hot”,”dot”,”dog”,”lot”,”log”,”cog”]

Output:
[
  [“hit”,”hot”,”dot”,”dog”,”cog”],
  [“hit”,”hot”,”lot”,”log”,”cog”]
]


Example 2:

Input:
beginWord = “hit”
endWord = “cog”
wordList = [“hot”,”dot”,”dog”,”lot”,”log”]

Output: []

*Explanation: The endWord “cog” is not in wordList, therefore no possibletransformation.


题目大意：

给定一个字典和两个单词。每次变换一个字母的得到新单词且该词要在字典中。求所有最少的变换路径。

解题思路：

更难于Leetcode 127，BFS用于找最短路径而DFS找路径，此题正是贯彻这一思想，先用BFS找出最短路径，
然后根据最短路径值找出所有路径。找BFS解的同时建图用邻接表表示Map>(这是
部分图，与解相关的图)和解集合Map(从始点到不同节点的最短距离)，这两个信息正是
Dijkistra的图输入和解。DFS从始点开始遍历邻接节点，确保沿着最短路径走，最短路径为
map.get(cur)+1=map.get(next)表示当前节点到始点距离+1=儿节点到始点距离，终止条件为找到目标节点。

  1. 在遍历所有邻接节点的时候，如果不加筛选对所有邻接节点都做DFS会造成LTE。关键是要利用BFS中所有
    节点到单源的最短路径来剪枝。只需DFS最短路径上的节点，否则跳过。
  2. 利用了单源最短路径映射表distance后，不需要记录visited，因为重复的节点不会在最短路劲上。
  3. Cache nextWords的结果。

解题步骤：

这题是最短路径题，第一时间想到BFS。这是一条典型的单源最短路径问题。

  1. 建字典。
  2. BFS访问，得到图和单源最短路径Map，以及最短路径距离。同时建立邻接表graph[word] = neighbors，DFS时候不用再次找相邻单词
  3. DFS求路径，按最短路径剪枝dict[neighbor] == dict[startWord] + 1。

注意事项：

  1. 注意题目条件，开始词不在字典中(终结词默认在，否则无结果），要将它加入字典中且距离为1且要加入到path，Line 10。
  2. 建图的邻接表，对没有边的节点也要加到邻接表，所以先对所有点赋空列表，再根据边更新值，Line 29。用defaultdict(list)可解决
  3. DFS模板中去掉visited部分，因为用了最短距离distance的map来指导访问路径，所以不会存在循环的情况(否则不会是最短距离)
    而且如果有visited会存在丢解，因为如果一个节点不在最短路径上先被访问就会被标记为visited，真正到最短路径上时就会返回。
    DFS模板中加入if dict[neighbor] == dict[startWord] + 1来剪边。

Python代码：

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
def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[int]]:
	if not beginWord or not endWord:
		return 0
	distance, graph = {}, defaultdict(list)
	for word in wordList:
		distance[word] = 0
	distance[beginWord] = 1
	self.bfs(beginWord, endWord, distance, graph, set())
	result = []
	self.dfs(graph, beginWord, endWord, [beginWord], result, distance) # remember [beginWord]
	return result

def dfs(self, graph, startWord, endWord, path, res, dict):
	if startWord == endWord:
		res.append(list(path))
		return
	'''if startWord in visited: # remember
		return
	visited.add(startWord)'''
	for neighbor in graph[startWord]:
		if dict[neighbor] == dict[startWord] + 1:
			path.append(neighbor)
			self.dfs(graph, neighbor, endWord, path, res, dict)
			path.pop()

def bfs(self, beginWord, endWord, dict, graph, visited):
	queue = deque([beginWord])
	visited.add(beginWord)
	# for key in dict.keys():  # remember
	#    graph[key] = []
	while queue:
		word = queue.popleft()
		if word == endWord:
			return dict[word]

		neighbors = self.get_next_words(word, dict)
		graph[word] = neighbors
		for neighbor in neighbors:
			if neighbor not in visited:
				queue.append(neighbor)
				visited.add(neighbor)
				dict[neighbor] = dict[word] + 1
	return 0

def get_next_words(self, word, dict):
	res = []
	for i in range(len(word)):
		for c in string.ascii_lowercase: # or use 'abcdefghijklmnopqrstuvwxyz'
			if c == word[i]:
				continue
			new_word = word[:i] + c + word[i + 1:]
			if new_word in dict:
				res.append(new_word)
	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
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
73
74
75
76
77
78
79
80
81
82
83
84
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
	List<String> path = new ArrayList<>();
	List<List<String>> res = new ArrayList<>();
	if(beginWord == null || endWord == null)
		return res;
	
	// This is a dict and also keeps track of distance
	Map<String, Integer> dict = getDict(wordList);
	// Make sure endWord is in the dict and can be the next word 
	//dict.put(endWord, 0);
	dict.put(beginWord, 1);
	HashMap<String, List<String>> graph = new HashMap<String, List<String>>();
	ladderLength(beginWord, endWord, dict, graph);
	path.add(beginWord);
	dfs(beginWord, endWord, dict, graph, path, res);
	return res;
}

void dfs(String cur, String endWord, Map<String, Integer> distance,
		HashMap<String, List<String>> graph, List<String> path, List<List<String>> res) {
	if(endWord.equals(cur)) {
		res.add(new ArrayList<>(path));
		return;
	}
	for(String word : graph.get(cur)) {
		path.add(word);
		if(distance.get(word) - 1 == distance.get(cur)) // use distance, resolve LTE the most important
			dfs(word, endWord, distance, graph, path, res);
		path.remove(path.size() - 1);
	}
}

// cache getNextWords
int ladderLength(String beginWord, String endWord, Map<String, Integer> dict, Map<String, List<String>> graph) {
	Set<String> visited = new HashSet<>();
	Queue<String> q = new LinkedList<>();
	q.offer(beginWord);
	visited.add(beginWord);
	for(String s : dict.keySet()) {// remember
		graph.put(s, new ArrayList<>());
	}
	while(!q.isEmpty()) {
		String word = q.poll();
		if(endWord.equals(word))
			return dict.get(word);
		
		List<String> nextWords = getNextWords(word, dict);
		graph.put(word, new ArrayList<>(nextWords));
		for(String s : nextWords) {
			if(visited.contains(s))
				continue;
			
			q.offer(s);
			visited.add(s);
			dict.put(s, dict.get(word) + 1);
		}
	}
	return 0;
}

Map<String, Integer> getDict(List<String> wordList) {
	Map<String, Integer> map = new HashMap<>();
	for(String word : wordList) {
		map.put(word, 0);
	}
	return map;
}

List<String> getNextWords(String word, Map<String, Integer> dict) {
	List<String> result = new ArrayList<>();
	for(int i = 0; i < word.length(); i++) {
		for(int j = 0; j < 26; j++) { 
			char newChar = (char)('a' + j);
			if(word.charAt(i) == newChar) // exclude itself
				continue;
			String newWord = word.substring(0, i) + 
					newChar + word.substring(i + 1, word.length());
			if(dict.containsKey(newWord))
				result.add(newWord);
			
		}
	}
	return result;
}

算法分析：

getNextWords是L26L=O(L2)产生新字符串需要L
时间复杂度为O(nL2 + mk)，空间复杂度O(n)，m为答案个数, k为最短路径值，n为单词数。

Posted on Edited on Disqus:

LeetCode 368 Largest Divisible Subset

Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies:

Si % Sj = 0 or Sj % Si = 0.

If there are multiple solutions, return any subset is fine.

Example 1:

**Input:** [1,2,3]
**Output:** [1,2] (of course, [1,3] will also be ok)

Example 2:

**Input:** [1,2,4,8]
**Output:** [1,2,4,8]

题目大意：

一个数组，让我们求这样一个子集合，集合中的任意两个数相互取余均为0。

解题思路：

由于知道子问题有助于求解考虑用DP。它就是LIS的翻版。这道题还需要打印DP路径。

  1. 定义dp[i]为num[i-1]这个数对应的最大可整除子集合个数。
  2. 递归式为dp[i] = max{dp[j-1] + 1}, 0<j<i, 若num[i-1]可被num[j-1]整除
  3. 方向为从左到右。初始值为dp = 1。
  4. path数组记录解的下标+1，每求得一个解dp[i] = dp[j] + 1就记录对应上一层解的下标，也就是到此解的路径。

注意事项：

  1. 初始值dp = 1。

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 List<Integer> largestDivisibleSubset(int[] nums) {
	List<Integer> res = new ArrayList<>();
	if(nums == null || nums.length == 0)
		return res;
	if(nums.length == 1)
		return Arrays.asList(nums[0]);
	Arrays.sort(nums);
	int max = Integer.MIN_VALUE;
	int maxPos = -1;
	int[] dp = new int[nums.length + 1];
	int[] path = new int[nums.length + 1];
	for(int i = 0; i < dp.length; i++) // remember to init to 1
		dp[i] = 1;
	for(int i = 1; i < dp.length; i++) {
		for(int j = 1; j < i; j++) {
			if(nums[i-1] % nums[j-1] == 0 && dp[j] + 1 > dp[i]) {
				dp[i] = dp[j] + 1;
				path[i] = j;
			}
		}
		if(dp[i] > max) { // the biggest value might not be the last one, keep track of the start pos for the path
			max = dp[i];
			maxPos = i;
		}
	}
	int pos = maxPos;
	for(int i = 0; i < dp[maxPos]; i++) {
		res.add(nums[pos-1]);
		pos = path[pos];
		
	}
	Collections.sort(res);
	return res;
}

算法分析：

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

Posted on Edited on Disqus:

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)。

Posted on Edited on Disqus:

LeetCode 2080 Range Frequency Queries

Design a data structure to find the frequency of a given value in a given subarray.

The frequency of a value in a subarray is the number of occurrences of that value in the subarray.

Implement the RangeFreqQuery class:

  • RangeFreqQuery(int[] arr) Constructs an instance of the class with the given 0-indexed integer array arr.
  • int query(int left, int right, int value) Returns the frequency of value in the subarray arr[left...right].

A subarray is a contiguous sequence of elements within an array. arr[left...right] denotes the subarray that contains the elements of nums between indices left and right (inclusive).

Example 1:

**Input**
["RangeFreqQuery", "query", "query"]
[[[12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]], [1, 2, 4], [0, 11, 33]]
**Output**
[null, 1, 2]

**Explanation**
RangeFreqQuery rangeFreqQuery = new RangeFreqQuery([12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]);
rangeFreqQuery.query(1, 2, 4); // return 1\. The value 4 occurs 1 time in the subarray [33, 4]
rangeFreqQuery.query(0, 11, 33); // return 2\. The value 33 occurs 2 times in the whole array.

Constraints:

  • 1 <= arr.length <= 10<sup>5</sup>
  • 1 <= arr[i], value <= 10<sup>4</sup>
  • 0 <= left <= right < arr.length
  • At most 10<sup>5</sup> calls will be made to query

题目大意：

设计数据结构，支持在指定的子数组中某target的频数。

解题思路：

这题有意思，有望成为经典题。第一种方法写用以每个字母为结尾的frequency_dict作为数据结构，query只需要用frequency_dict[right]-frequency_dict[left-1]，
空间复杂度为O(n2)得到TLE。第二种方法用bucket sort，就是将值作为key存到dict中，而value是下标List，query时候得到对应List，遍历
一次即可，但仍然得到TLE。第三种方法改进用Binary search得到下标List的左右界。二分法用greater_or_equal_position以及small_or_equal_position.
所以最终方案采取bucket sort + binary search

解题步骤：

  1. dict记录值到下标列表的映射
  2. 二分法找left和right的index从而求个数

注意事项：

  1. Binary search用greater_or_equal_position以及small_or_equal_position.

Python代码：

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
class RangeFreqQuery:
	
    def __init__(self, arr: List[int]):
        self.frequency_dict = {}

        for i, n in enumerate(arr):
            if n not in self.frequency_dict:
                self.frequency_dict[n] = [i]
            else:
                self.frequency_dict[n].append(i)

    def query(self, left: int, right: int, value: int) -> int:
        if value not in self.frequency_dict:
            return 0
        index_list = self.frequency_dict[value]
        '''
        count = 0
        for index in index_list:
            if left <= index <= right:
                count += 1
        '''
        left_pos = self.greater_or_equal_position(index_list, left)
        right_pos = self.smaller_or_equal_position(index_list, right)
        if left_pos == -1 or right_pos == -1:
            return 0
        return right_pos - left_pos + 1

    def greater_or_equal_position(self, nums: List[int], target: int) -> int:
        if not nums:
            return -1
        start, end = 0, len(nums) - 1
        while start + 1 < end:
            mid = start + (end - start) // 2
            if target > nums[mid]:
                start = mid
            elif target < nums[mid]:
                end = mid
            else:
                start = mid
        if nums[start] >= target:
            return start
        if nums[end] >= target:
            return end
        return -1

    def smaller_or_equal_position(self, nums: List[int], target: int) -> int:
        if not nums:
            return -1
        start, end = 0, len(nums) - 1
        while start + 1 < end:
            mid = start + (end - start) // 2
            if target > nums[mid]:
                start = mid
            elif target < nums[mid]:
                end = mid
            else:
                end = mid
        if nums[end] <= target:
            return end
        if nums[start] <= target:
            return start
        return -1

用defaultdict(list)和bisect来优化程序

Python代码：

1
2
3
4
5
6
7
8
9
10
11
def __init__(self, arr: List[int]):
	self.frequency_dict = collections.defaultdict(list)

	for i, n in enumerate(arr):
		self.frequency_dict[n].append(i)

def query(self, left: int, right: int, value: int) -> int:
	index_list = self.frequency_dict[value]
	left_pos = bisect.bisect(index_list, left - 1)
	right_pos = bisect.bisect(index_list, right)
	return right_pos - left_pos

算法分析：

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

Posted on Edited on Disqus:

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
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)):
		heappush(res, freq_dict[i])
		if len(res) > k:
			heappop(res)

	return [k for v, k in res]

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

1
2
3
4
5
6
7
8
9
10
11
12
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)):
		heappush(res, freq_dict[i])
		if len(res) > k:
			heappop(res)
	return [k for v, k 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;
 }
Free mock interview