本文解决的问题: 按主题归纳 二分查找、栈、堆 相关高频题型与通用解法。
适用范围: 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 2 输入:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 输出:true
示例 2:
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) { 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 <= 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:
1 2 3 输入:heights = [2,1,5,6,2,3] 输出:10 解释:最大的矩形为图中红色区域,面积为 10
示例 2:
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; } }
堆 给定整数数组 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]; } 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; } }
给你一个整数数组 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) { qsort(values, start, index - 1 , ret, retIndex, k); } else { 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 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 ]); } } }
参考资料