本文解决的问题: 按主题归纳 二分查找、栈、堆 相关高频题型与通用解法。

适用范围: LeetCode 中文站题目,示例主要使用 Java。

阅读建议: 先识别数据结构与不变量,再结合题目约束选择算法,不要只记忆代码。

二分查找

搜索二维矩阵(中等)

给你一个满足下述两条属性的 m x n 整数矩阵:

  • 每行中的整数从左到右按非严格递增顺序排列。
  • 每行的第一个整数大于前一行的最后一个整数。

给你一个整数 target ,如果 target 在矩阵中,返回 true ;否则,返回 false 。

提示:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 100
  • -104 <= matrix[i][j], target <= 104

示例 1:

1. 搜索二维矩阵(中)示例

1
2
输入:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出:true

示例 2:

1. 搜索二维矩阵(中)示例

1
2
输入:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出:false

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public boolean searchMatrix(int[][] matrix, int target) {
int cols = matrix[0].length, rows = matrix.length;
while (rows > 0) {
int left = 0, right = cols - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (matrix[rows - 1][mid] == target) {
return true;
} else if (matrix[rows - 1][mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
rows --;
}
return false;
}

搜索插入位置(简单)

给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

提示:

  • 1 <= nums.length <= 10^4
  • -10^4 <= nums[i] <= 10^4
  • nums 为 **无重复元素 **的 **升序 **排列数组
  • -10^4 <= target <= 10^4

示例 1:

1
2
输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:

1
2
输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:

1
2
输入: nums = [1,3,5,6], target = 7
输出: 4

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public int searchInsert(int[] nums, int target) {
int n = nums.length;
int left = 0, right = n - 1, ans = n;
while (left <= right) {
int mid = ((right - left) >> 1) + left;
if (target <= nums[mid]) {
ans = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return ans;
}
}

在排序数组中查找元素的第一个和最后一个位置(简单)

给你一个按照非递减顺序排列的整数数组 nums,和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target,返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

提示:

  • 0 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9
  • nums 是一个非递减数组
  • -10^9 <= target <= 10^9

示例 1:

1
2
输入:nums = [5,7,7,8,8,10], target = 8
输出:[3,4]

示例 2:

1
2
输入:nums = [5,7,7,8,8,10], target = 6
输出:[-1,-1]

示例 3:

1
2
输入:nums = [], target = 0
输出:[-1,-1]

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public int[] searchRange(int[] nums, int target) {
int leftIdx = binarySearch(nums, target, true);
int rightIdx = binarySearch(nums, target, false) - 1;
if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target && nums[rightIdx] == target) {
return new int[]{leftIdx, rightIdx};
}
return new int[]{-1, -1};
}

public int binarySearch(int[] nums, int target, boolean lower) {
int left = 0, right = nums.length - 1, ans = nums.length;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] > target || (lower && nums[mid] >= target)) {
right = mid - 1;
ans = mid;
} else {
left = mid + 1;
}
}
return ans;
}
}

搜索旋转排序数组(中等)

整数数组 nums 按升序排列,数组中的值 互不相同 。

在传递给函数之前,nums 在预先未知的某个下标 k(0 <= k < nums.length)上进行了 旋转 ,使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]](下标 从 0 开始 计数)。例如, [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ,如果 nums 中存在这个目标值 target ,则返回它的下标,否则返回 -1 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

提示:

  • 1 <= nums.length <= 5000
  • -10^4 <= nums[i] <= 10^4
  • nums 中的每个值都 独一无二
  • 题目数据保证 nums 在预先未知的某个下标上进行了旋转
  • -10^4 <= target <= 10^4

示例 1:

1
2
输入:nums = [4,5,6,7,0,1,2], target = 0
输出:4

示例 2:

1
2
输入:nums = [4,5,6,7,0,1,2], target = 3
输出:-1

示例 3:

1
2
输入:nums = [1], target = 0
输出:-1

代码:

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
class Solution {
public int search(int[] nums, int target) {
int n = nums.length;
if (n == 0) {
return -1;
}
if (n == 1) {
return nums[0] == target ? 0 : -1;
}
int l = 0, r = n - 1;
while (l <= r) {
int mid = (l + r) / 2;
if (nums[mid] == target) {
return mid;
}
if (nums[0] <= nums[mid]) {
if (nums[0] <= target && target < nums[mid]) {
r = mid - 1;
} else {
l = mid + 1;
}
} else {
if (nums[mid] < target && target <= nums[n - 1]) {
l = mid + 1;
} else {
r = mid - 1;
}
}
}
return -1;
}
}

寻找旋转排序数组中的最小值(中等)

已知一个长度为 n 的数组,预先按照升序排列,经由 1 到 n 次 旋转 后,得到输入数组。例如,原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到:* 若旋转 4 次,则可以得到 [4,5,6,7,0,1,2]

  • 若旋转 7 次,则可以得到 [0,1,2,4,5,6,7]

注意,数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

给你一个元素值 互不相同 的数组 nums ,它原来是一个升序排列的数组,并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

提示:

  • n == nums.length
  • 1 <= n <= 5000
  • -5000 <= nums[i] <= 5000
  • nums 中的所有整数 互不相同
  • nums 原来是一个升序排序的数组,并进行了 1 至 n 次旋转

示例 1:

1
2
3
输入:nums = [3,4,5,1,2]
输出:1
解释:原数组为 [1,2,3,4,5] ,旋转 3 次得到输入数组。

示例 2:

1
2
3
输入:nums = [4,5,6,7,0,1,2]
输出:0
解释:原数组为 [0,1,2,4,5,6,7] ,旋转 4 次得到输入数组。

示例 3:

1
2
3
输入:nums = [11,13,15,17]
输出:11
解释:原数组为 [11,13,15,17] ,旋转 4 次得到输入数组。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public int findMin(int[] nums) {
int low = 0;
int high = nums.length - 1;
while (low < high) {
int pivot = low + (high - low) / 2;
if (nums[pivot] < nums[high]) {
high = pivot;
} else {
low = pivot + 1;
}
}
return nums[low];
}
}

寻找两个正序数组的中位数(困难)

给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

提示:

  • nums1.length == m
  • nums2.length == n
  • 0 <= m <= 1000
  • 0 <= n <= 1000
  • 1 <= m + n <= 2000
  • -10^6 <= nums1[i], nums2[i] <= 10^6

示例 1:

1
2
3
输入:nums1 = [1,3], nums2 = [2]
输出:2.00000
解释:合并数组 = [1,2,3] ,中位数 2

示例 2:

1
2
3
输入:nums1 = [1,2], nums2 = [3,4]
输出:2.50000
解释:合并数组 = [1,2,3,4] ,中位数 (2 + 3) / 2 = 2.5

代码:

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
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int length1 = nums1.length, length2 = nums2.length;
int totalLength = length1 + length2;
if (totalLength % 2 == 1) {
int midIndex = totalLength / 2;
double median = getKthElement(nums1, nums2, midIndex + 1);
return median;
} else {
int midIndex1 = totalLength / 2 - 1, midIndex2 = totalLength / 2;
double median = (getKthElement(nums1, nums2, midIndex1 + 1) + getKthElement(nums1, nums2, midIndex2 + 1)) / 2.0;
return median;
}
}

public int getKthElement(int[] nums1, int[] nums2, int k) {
/* 主要思路:要找到第 k (k>1) 小的元素,那么就取 pivot1 = nums1[k/2-1] 和 pivot2 = nums2[k/2-1] 进行比较
* 这里的 "/" 表示整除
* nums1 中小于等于 pivot1 的元素有 nums1[0 .. k/2-2] 共计 k/2-1 个
* nums2 中小于等于 pivot2 的元素有 nums2[0 .. k/2-2] 共计 k/2-1 个
* 取 pivot = min(pivot1, pivot2),两个数组中小于等于 pivot 的元素共计不会超过 (k/2-1) + (k/2-1) <= k-2 个
* 这样 pivot 本身最大也只能是第 k-1 小的元素
* 如果 pivot = pivot1,那么 nums1[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除",剩下的作为新的 nums1 数组
* 如果 pivot = pivot2,那么 nums2[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除",剩下的作为新的 nums2 数组
* 由于我们 "删除" 了一些元素(这些元素都比第 k 小的元素要小),因此需要修改 k 的值,减去删除的数的个数
*/

int length1 = nums1.length, length2 = nums2.length;
int index1 = 0, index2 = 0;
int kthElement = 0;

while (true) {
// 边界情况
if (index1 == length1) {
return nums2[index2 + k - 1];
}
if (index2 == length2) {
return nums1[index1 + k - 1];
}
if (k == 1) {
return Math.min(nums1[index1], nums2[index2]);
}

// 正常情况
int half = k / 2;
int newIndex1 = Math.min(index1 + half, length1) - 1;
int newIndex2 = Math.min(index2 + half, length2) - 1;
int pivot1 = nums1[newIndex1], pivot2 = nums2[newIndex2];
if (pivot1 <= pivot2) {
k -= (newIndex1 - index1 + 1);
index1 = newIndex1 + 1;
} else {
k -= (newIndex2 - index2 + 1);
index2 = newIndex2 + 1;
}
}
}
}

栈

有效的括号

给定一个只包括 '(',')','{','}','[',']' 的字符串 s ,判断字符串是否有效。

有效字符串需满足:

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

提示:

  • 1 <= s.length <= 104
  • s 仅由括号 '()[]{}' 组成

示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
示例 1:
输入:s = "()"
输出:true

示例 2:
输入:s = "()[]{}"
输出:true

示例 3:
输入:s = "(]"
输出:false

示例 4:
输入:s = "([])"
输出:true

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public boolean isValid(String s) {
if (s.length() % 2 != 0) {
return false;
}
Map<Character, Character> map = new HashMap<>(){{
put(')', '(');
put(']', '[');
put('}', '{');
}};
Deque<Character> stack = new LinkedList<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (map.containsKey(c)) {
if (stack.isEmpty() || map.get(c) != stack.peek()) {
return false;
}
stack.pop();
} else {
stack.push(c);
}
}
return stack.isEmpty();
}

最小栈

设计一个支持 push ,pop ,top 操作,并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

  • MinStack() 初始化堆栈对象。
  • void push(int val) 将元素val推入堆栈。
  • void pop() 删除堆栈顶部的元素。
  • int top() 获取堆栈顶部的元素。
  • int getMin() 获取堆栈中的最小元素。

提示:

  • -231 <= val <= 231 - 1
  • pop、top 和 getMin 操作总是在 非空栈 上调用
  • push, pop, top, and getMin最多被调用 3 * 104 次

示例 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
输入:
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出:
[null,null,null,null,-3,null,0,-2]

解释:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.

代码:

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
class MinStack {
Deque<Integer> xStack;
Deque<Integer> minStack;

public MinStack() {
xStack = new LinkedList<Integer>();
minStack = new LinkedList<Integer>();
minStack.push(Integer.MAX_VALUE);
}

public void push(int x) {
xStack.push(x);
minStack.push(Math.min(minStack.peek(), x));
}

public void pop() {
xStack.pop();
minStack.pop();
}

public int top() {
return xStack.peek();
}

public int getMin() {
return minStack.peek();
}
}

字符串解码(中等)

给定一个经过编码的字符串,返回它解码后的字符串。

编码规则为: k[encoded_string],表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的;输入字符串中没有额外的空格,且输入的方括号总是符合格式要求的。

此外,你可以认为原始数据不包含数字,所有的数字只表示重复的次数 k ,例如不会出现像 3a 或 2[4] 的输入。

提示:

  • 1 <= s.length <= 30
  • s 由小写英文字母、数字和方括号 '[]' 组成
  • s 保证是一个 有效 的输入。
  • s 中所有整数的取值范围为 [1, 300]

示例 1:

1
2
输入:s = "3[a]2[bc]"
输出:"aaabcbc"

示例 2:

1
2
输入:s = "3[a2[c]]"
输出:"accaccacc"

示例 3:

1
2
输入:s = "2[abc]3[cd]ef"
输出:"abcabccdcdcdef"

示例 4:

1
2
输入:s = "abc3[cd]xyz"
输出:"abccdcdcdxyz"

代码:

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
class Solution {
public String decodeString(String s) {
StringBuilder res = new StringBuilder();
int multi = 0;
LinkedList<Integer> stack_multi = new LinkedList<>();
LinkedList<String> stack_res = new LinkedList<>();
for(Character c : s.toCharArray()) {
if(c == '[') {
stack_multi.addLast(multi);
stack_res.addLast(res.toString());
multi = 0;
res = new StringBuilder();
}
else if(c == ']') {
StringBuilder tmp = new StringBuilder();
int cur_multi = stack_multi.removeLast();
for(int i = 0; i < cur_multi; i++) tmp.append(res);
res = new StringBuilder(stack_res.removeLast() + tmp);
}
else if(c >= '0' && c <= '9') multi = multi * 10 + Integer.parseInt(c + "");
else res.append(c);
}
return res.toString();
}
}


// 递归
class Solution {
public String decodeString(String s) {
return dfs(s, 0)[0];
}
private String[] dfs(String s, int i) {
StringBuilder res = new StringBuilder();
int multi = 0;
while(i < s.length()) {
if(s.charAt(i) >= '0' && s.charAt(i) <= '9')
multi = multi * 10 + Integer.parseInt(String.valueOf(s.charAt(i)));
else if(s.charAt(i) == '[') {
String[] tmp = dfs(s, i + 1);
i = Integer.parseInt(tmp[0]);
while(multi > 0) {
res.append(tmp[1]);
multi--;
}
}
else if(s.charAt(i) == ']')
return new String[] { String.valueOf(i), res.toString() };
else
res.append(String.valueOf(s.charAt(i)));
i++;
}
return new String[] { res.toString() };
}
}

每日温度(中等)

给定一个整数数组 temperatures ,表示每天的温度,返回一个数组 answer ,其中 answer[i] 是指对于第 i 天,下一个更高温度出现在几天后。如果气温在这之后都不会升高,请在该位置用 0 来代替。

提示:

  • 1 <= temperatures.length <= 10^5
  • 30 <= temperatures[i] <= 100

示例 1:

1
2
输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

示例 2:

1
2
输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]

示例 3:

1
2
输入: temperatures = [30,60,90]
输出: [1,1,0]

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int length = temperatures.length;
int[] ans = new int[length];
Deque<Integer> stack = new LinkedList<Integer>();
for (int i = 0; i < length; i++) {
int temperature = temperatures[i];
while (!stack.isEmpty() && temperature > temperatures[stack.peek()]) {
int prevIndex = stack.pop();
ans[prevIndex] = i - prevIndex;
}
stack.push(i);
}
return ans;
}
}

柱状图中最大的矩形(困难)

给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。

求在该柱状图中,能够勾勒出来的矩形的最大面积。

提示:

  • 1 <= heights.length <=10^5
  • 0 <= heights[i] <= 10^4

示例 1:

5. 柱状图中最大的矩形(难)示例

1
2
3
输入:heights = [2,1,5,6,2,3]
输出:10
解释:最大的矩形为图中红色区域,面积为 10

示例 2:

5. 柱状图中最大的矩形(难)示例

1
2
输入: heights = [2,4]
输出: 4

代码:

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
class Solution {
public int largestRectangleArea(int[] heights) {
int n = heights.length;
int[] left = new int[n];
int[] right = new int[n];

Deque<Integer> mono_stack = new ArrayDeque<Integer>();
for (int i = 0; i < n; ++i) {
while (!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) {
mono_stack.pop();
}
left[i] = (mono_stack.isEmpty() ? -1 : mono_stack.peek());
mono_stack.push(i);
}

mono_stack.clear();
for (int i = n - 1; i >= 0; --i) {
while (!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) {
mono_stack.pop();
}
right[i] = (mono_stack.isEmpty() ? n : mono_stack.peek());
mono_stack.push(i);
}

int ans = 0;
for (int i = 0; i < n; ++i) {
ans = Math.max(ans, (right[i] - left[i] - 1) * heights[i]);
}
return ans;
}
}

// 常数优化
class Solution {
public int largestRectangleArea(int[] heights) {
int n = heights.length;
int[] left = new int[n];
int[] right = new int[n];
Arrays.fill(right, n);

Deque<Integer> mono_stack = new ArrayDeque<Integer>();
for (int i = 0; i < n; ++i) {
while (!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) {
right[mono_stack.peek()] = i;
mono_stack.pop();
}
left[i] = (mono_stack.isEmpty() ? -1 : mono_stack.peek());
mono_stack.push(i);
}

int ans = 0;
for (int i = 0; i < n; ++i) {
ans = Math.max(ans, (right[i] - left[i] - 1) * heights[i]);
}
return ans;
}
}

堆

数组中的第K个最大元素(中等)

给定整数数组 nums 和整数 k,请返回数组中第 **k** 个最大的元素。

请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

提示:

  • 1 <= k <= nums.length <= 105
  • -104 <= nums[i] <= 104

示例 1:

1
2
输入: [3,2,1,5,6,4], k = 2
输出: 5

示例 2:

1
2
输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4

代码:

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
class Solution {
public int findKthLargest(int[] nums, int k) {
Arrays.sort(nums);
return nums[nums.length - k];
}

/**
我们也可以使用堆排序来解决这个问题——建立一个大根堆,做 k−1 次删除操作后堆顶元素就是我们要找的答案。在很多语言中,都有优先队列或者堆的的容器可以直接使用,但是在面试中,面试官更倾向于让更面试者自己实现一个堆。所以建议读者掌握这里大根堆的实现方法,在这道题中尤其要搞懂「建堆」、「调整」和「删除」的过程。
**/
public int findKthLargest(int[] nums, int k) {
int heapSize = nums.length;
buildMaxHeap(nums, heapSize);
for (int i = nums.length - 1; i >= nums.length - k + 1; --i) {
swap(nums, 0, i);
--heapSize;
maxHeapify(nums, 0, heapSize);
}
return nums[0];
}

public void buildMaxHeap(int[] a, int heapSize) {
for (int i = heapSize / 2 - 1; i >= 0; --i) {
maxHeapify(a, i, heapSize);
}
}

public void maxHeapify(int[] a, int i, int heapSize) {
int l = i * 2 + 1, r = i * 2 + 2, largest = i;
if (l < heapSize && a[l] > a[largest]) {
largest = l;
}
if (r < heapSize && a[r] > a[largest]) {
largest = r;
}
if (largest != i) {
swap(a, i, largest);
maxHeapify(a, largest, heapSize);
}
}

public void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}

前 K 个高频元素(中等)

给你一个整数数组 nums 和一个整数 k ,请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

提示:

  • 1 <= nums.length <= 10^5
  • k 的取值范围是 [1, 数组中不相同的元素的个数]
  • 题目数据保证答案唯一,换句话说,数组中前 k 个高频元素的集合是唯一的

进阶: 你所设计算法的时间复杂度 必须 优于 O(n log n) ,其中 n 是数组大小。

示例 1:

1
2
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

1
2
输入: nums = [1], k = 1
输出: [1]

代码:

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
// 基于快速排序
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> occurrences = new HashMap<Integer, Integer>();
for (int num : nums) {
occurrences.put(num, occurrences.getOrDefault(num, 0) + 1);
}
// 获取每个数字出现次数
List<int[]> values = new ArrayList<int[]>();
for (Map.Entry<Integer, Integer> entry : occurrences.entrySet()) {
int num = entry.getKey(), count = entry.getValue();
values.add(new int[]{num, count});
}
int[] ret = new int[k];
qsort(values, 0, values.size() - 1, ret, 0, k);
return ret;
}

public void qsort(List<int[]> values, int start, int end, int[] ret, int retIndex, int k) {
int picked = (int) (Math.random() * (end - start + 1)) + start;
Collections.swap(values, picked, start);

int pivot = values.get(start)[1];
int index = start;
for (int i = start + 1; i <= end; i++) {
// 使用双指针把不小于基准值的元素放到左边,
// 小于基准值的元素放到右边
if (values.get(i)[1] >= pivot) {
Collections.swap(values, index + 1, i);
index++;
}
}
Collections.swap(values, start, index);

if (k <= index - start) {
// 前 k 大的值在左侧的子数组里
qsort(values, start, index - 1, ret, retIndex, k);
} else {
// 前 k 大的值等于左侧的子数组全部元素
// 加上右侧子数组中前 k - (index - start + 1) 大的值
for (int i = start; i <= index; i++) {
ret[retIndex++] = values.get(i)[0];
}
if (k > index - start + 1) {
qsort(values, index + 1, end, ret, retIndex, k - (index - start + 1));
}
}
}
}

数据流的中位数(困难)

中位数是有序整数列表中的中间值。如果列表的大小是偶数,则没有中间值,中位数是两个中间值的平均值。

  • 例如 arr = [2,3,4] 的中位数是 3 。
  • 例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。

实现 MedianFinder 类:

  • MedianFinder() 初始化 MedianFinder 对象。
  • void addNum(int num) 将数据流中的整数 num 添加到数据结构中。
  • double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10^-5 以内的答案将被接受。

提示:

  • -10^5 <= num <= 10^5
  • 在调用 findMedian 之前,数据结构中至少有一个元素
  • 最多 5 * 10^4 次调用 addNum 和 findMedian

示例 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
输入
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
输出
[null, null, null, 1.5, null, 2.0]

解释
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1); // arr = [1]
medianFinder.addNum(2); // arr = [1, 2]
medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
medianFinder.addNum(3); // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

代码:

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
/**
我们也可以使用有序集合维护这些数。我们把有序集合看作自动排序的数组,使用双指针指向有序集合中的中位数元素即可。当累计添加的数的数量为奇数时,双指针指向同一个元素。当累计添加的数的数量为偶数时,双指针分别指向构成中位数的两个数。

当我们尝试添加一个数 num 到数据结构中,我们需要分情况讨论:

初始有序集合为空时,我们直接让左右指针指向 num 所在的位置。

有序集合为中元素为奇数时,left 和 right 同时指向中位数。如果 num 小于等于中位数,那么只要让 left 左移,否则让 right 右移即可。

有序集合为中元素为偶数时,left 和 right 分别指向构成中位数的两个数。

当 num 成为新的唯一的中位数,那么我们让 left 右移,right 左移,这样它们即可指向 num 所在的位置;
当 num 大于等于 right,那么我们让 left 右移即可;
当 num 小于 right 指向的值,那么我们让 right 左移,注意到如果 num 恰等于 left 指向的值,那么 num 将被插入到 left 右侧,使得 left 和 right 间距增大,所以我们还需要额外让 left 指向移动后的 right。
**/
class MedianFinder {
TreeMap<Integer, Integer> nums;
int n;
int[] left;
int[] right;

public MedianFinder() {
nums = new TreeMap<Integer, Integer>();
n = 0;
left = new int[2];
right = new int[2];
}

public void addNum(int num) {
nums.put(num, nums.getOrDefault(num, 0) + 1);
if (n == 0) {
left[0] = right[0] = num;
left[1] = right[1] = 1;
} else if ((n & 1) != 0) {
if (num < left[0]) {
decrease(left);
} else {
increase(right);
}
} else {
if (num > left[0] && num < right[0]) {
increase(left);
decrease(right);
} else if (num >= right[0]) {
increase(left);
} else {
decrease(right);
System.arraycopy(right, 0, left, 0, 2);
}
}
n++;
}

public double findMedian() {
return (left[0] + right[0]) / 2.0;
}

private void increase(int[] iterator) {
iterator[1]++;
if (iterator[1] > nums.get(iterator[0])) {
iterator[0] = nums.ceilingKey(iterator[0] + 1);
iterator[1] = 1;
}
}

private void decrease(int[] iterator) {
iterator[1]--;
if (iterator[1] == 0) {
iterator[0] = nums.floorKey(iterator[0] - 1);
iterator[1] = nums.get(iterator[0]);
}
}
}

参考资料