算法的解题模式Ⅲ

7. 前K大（小）元素（Top ‘K’ Elements） 方法一：排序法

思路：先对整个数组进行排序，然后取排序后数组的前（后） K 个元素。

方法二：堆（优先队列）法

思路：使用一个最小堆来维护前 K 小（大）的元素。遍历数组，当堆的大小小于 K 时，直接将元素加入堆；当堆的大小达到 K 时，如果当前元素比堆顶元素小（大），则替换堆顶元素并调整堆。

力扣相关例题：

215. 数组中的第K个最大元素

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

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

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

class Solution { public int findKthLargest(int[] nums, int k) { Arrays.sort(nums); return nums[nums.length-k]; } }

347. 前 K 个高频元素 - 力扣

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

import java.util.*; class Solution { // 该方法用于找出数组 nums 中出现频率前 k 高的元素 public int[] topKFrequent(int[] nums, int k) { // 第一步：统计每个元素的出现频率 // 创建一个 HashMap 用于存储元素及其出现的频率 // 键为数组中的元素，值为该元素出现的次数 Map<Integer, Integer> map = new HashMap<>(); // 遍历数组 nums 中的每个元素 for (int num : nums) { // 使用 getOrDefault 方法获取元素的当前频率，如果元素不存在则默认为 0 // 然后将频率加 1 并更新到 map 中 map.put(num, map.getOrDefault(num, 0) + 1); } // 第二步：使用优先队列（小顶堆）来维护前 k 个高频元素 // 创建一个优先队列（小顶堆），队列中存储的元素是长度为 2 的数组 // 数组的第一个元素是元素本身，第二个元素是该元素的出现频率 // 优先队列按照元素的频率从小到大排序 PriorityQueue<int[]> pq = new PriorityQueue<>((pair1, pair2) -> pair1[1] - pair2[1]); // 遍历 map 中的每个键值对 for (Map.Entry<Integer, Integer> entry : map.entrySet()) { // 如果优先队列的大小小于 k，直接将当前元素及其频率加入队列 if (pq.size() < k) { pq.add(new int[]{entry.getKey(), entry.getValue()}); } // 如果优先队列的大小已经达到 k，并且当前元素的频率大于队列中最小频率的元素 else if (entry.getValue() > pq.peek()[1]) { // 移除队列中频率最小的元素 pq.poll(); // 将当前元素及其频率加入队列 pq.add(new int[]{entry.getKey(), entry.getValue()}); } } // 第三步：从优先队列中取出前 k 个高频元素 // 创建一个长度为 k 的数组用于存储结果 int[] ans = new int[k]; // 遍历优先队列，将队列中的元素依次取出 for (int i = 0; i < k; i++) { // 取出队列头部元素的第一个值（即元素本身）存入结果数组 ans[i] = pq.poll()[0]; } // 返回结果数组 return ans; } }

373. 查找和最小的 K 对数字 - 力扣

给定两个以 非递减顺序排列 的整数数组 nums1 和 nums2 , 以及一个整数 k 。

定义一对值 (u,v)，其中第一个元素来自 nums1，第二个元素来自 nums2 。

请找到和最小的 k 个数对 (u1,v1),  (u2,v2)  ...  (uk,vk) 。

import java.util.ArrayList; import java.util.List; import java.util.PriorityQueue; class Solution { /** * 此方法用于找出两个数组 nums1 和 nums2 中元素两两组合形成的和最小的前 k 对组合 * @param nums1 第一个整数数组 * @param nums2 第二个整数数组 * @param k 要找出的和最小的组合对数 * @return 包含和最小的前 k 对组合的列表 */ public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) { // 创建一个优先队列（最小堆），用于存储索引对 // 优先队列的大小初始化为 k // 优先队列的比较器根据索引对对应元素在 nums1 和 nums2 中的和来排序 // 和较小的索引对排在前面 PriorityQueue<int[]> pq = new PriorityQueue<>(k, (o1, o2) -> { return nums1[o1[0]] + nums2[o1[1]] - nums1[o2[0]] - nums2[o2[1]]; }); // 用于存储最终结果的列表，每个元素是一个包含两个整数的列表，表示一对组合 List<List<Integer>> ans = new ArrayList<>(); // 获取 nums1 数组的长度 int m = nums1.length; // 获取 nums2 数组的长度 int n = nums2.length; // 将 nums1 中前 Math.min(m, k) 个元素与 nums2 中第一个元素组成的索引对加入优先队列 // 因为对于每个 nums1 中的元素，先与 nums2 中最小的元素（即索引为 0 的元素）组合，可能得到较小的和 for (int i = 0; i < Math.min(m, k); i++) { // 索引对的第一个元素是 nums1 的索引，第二个元素是 nums2 的索引 pq.offer(new int[]{i, 0}); } // 循环 k 次，每次从优先队列中取出和最小的索引对，并将对应的元素组合加入结果列表 // 同时，如果取出的索引对在 nums2 中的索引可以向后移动（即不越界），则将新的索引对加入优先队列 while (k-- > 0 && !pq.isEmpty()) { // 从优先队列中取出和最小的索引对 int[] idxPair = pq.poll(); // 创建一个新的列表，用于存储当前取出的索引对对应的元素组合 List<Integer> list = new ArrayList<>(); // 将 nums1 中对应索引的元素加入列表 list.add(nums1[idxPair[0]]); // 将 nums2 中对应索引的元素加入列表 list.add(nums2[idxPair[1]]); // 将当前元素组合加入最终结果列表 ans.add(list); // 检查当前取出的索引对在 nums2 中的索引是否可以向后移动一位 if (idxPair[1] + 1 < n) { // 如果可以移动，将新的索引对（nums1 索引不变，nums2 索引加 1）加入优先队列 pq.offer(new int[]{idxPair[0], idxPair[1] + 1}); } } // 返回最终结果列表 return ans; } } 8. 区间重叠（Overlapping Intervals）

区间重叠模式用于合并或处理数组中的重叠区间。

在按起始时间排序的区间数组中，两个区间[a, b]和[c, d]重叠的条件是b >= c（即第一个区间的结束时间大于或等于第二个区间的起始时间）。

示例：输入：

list1 = [[1, 3], [5, 7]]list2 = [[2, 4], [6, 8]]

 输出：true

解释：list1 中的 [1, 3] 与 list2 中的 [2, 4] 重叠，list1 中的 [5, 7] 与 list2 中的 [6, 8] 重叠，所以返回 true。

解题思路

我们可以使用双重循环遍历两个区间列表，对于 list1 中的每个区间和 list2 中的每个区间，判断它们是否重叠。判断两个区间 [a1, b1] 和 [a2, b2] 重叠的条件是 Math.max(a1, a2) <= Math.min(b1, b2)。

力扣相关例题：

56. 合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

import java.util.Arrays; class Solution { /** * 该方法用于合并重叠的区间。给定一个二维数组 intervals，其中每个元素是一个长度为 2 的一维数组， * 表示一个区间的起始和结束位置。方法会将重叠的区间进行合并，并返回合并后的区间数组。 * @param intervals 包含多个区间的二维数组 * @return 合并重叠区间后的二维数组 */ public int[][] merge(int[][] intervals) { // 初始化一个二维数组 res，用于存储合并后的区间，其初始大小为 intervals 的长度 int[][] res = new int[intervals.length][2]; // 获取 intervals 数组的长度，即区间的数量 int n = intervals.length; // 对 intervals 数组按照每个区间的起始位置进行升序排序 // 使用 Lambda 表达式 (a, b) -> a[0] - b[0] 作为比较器 // 若 a[0] - b[0] < 0，则 a 排在 b 前面；若 a[0] - b[0] > 0，则 b 排在 a 前面 Arrays.sort(intervals, (a, b) -> a[0] - b[0]); // 初始化 index 为 -1，用于标记 res 数组中当前存储合并后区间的位置 int index = -1; // 遍历 intervals 数组中的每个区间 for (int i = 0; i < intervals.length; i++) { // 获取当前遍历到的区间 int[] cur = intervals[i]; // 如果 index 为 -1，说明 res 数组还没有存储任何区间，或者当前区间的起始位置大于 res 中最后一个区间的结束位置 // 意味着当前区间与之前合并的区间不重叠 if (index == -1 || cur[0] > res[index][1]) { // 增加 index，为存储新的区间做准备 index++; // 将当前区间直接存入 res 数组的 index 位置 res[index] = cur; } else { // 若当前区间与 res 中最后一个区间重叠，则更新 res 中最后一个区间的结束位置 // 取当前区间的结束位置和 res 中最后一个区间的结束位置的较大值 res[index][1] = Math.max(cur[1], res[index][1]); } } // 由于 res 数组的初始大小可能大于实际合并后的区间数量，使用 Arrays.copyOf 方法截取有效部分 // 从 res 数组中复制从索引 0 到 index + 1 的元素，得到最终合并后的区间数组 return Arrays.copyOf(res, index + 1); } }

57. 插入区间

给你一个 无重叠的 ，按照区间起始端点排序的区间列表 intervals，其中 intervals[i] = [starti, endi] 表示第 i 个区间的开始和结束，并且 intervals 按照 starti 升序排列。同样给定一个区间 newInterval = [start, end] 表示另一个区间的开始和结束。

在 intervals 中插入区间 newInterval，使得 intervals 依然按照 starti 升序排列，且区间之间不重叠（如果有必要的话，可以合并区间）。

返回插入之后的 intervals。

注意 你不需要原地修改 intervals。你可以创建一个新数组然后返回它。

import java.util.ArrayList; import java.util.List; class Solution { /** * 该方法用于将一个新的区间插入到已有的区间数组中，并合并可能重叠的区间。 * * @param intervals 已有的区间数组，每个区间由一个长度为 2 的整数数组表示，分别为区间的起始和结束位置。 * @param newInterval 要插入的新的区间，同样由一个长度为 2 的整数数组表示。 * @return 插入并合并重叠区间后的区间数组。 */ public int[][] insert(int[][] intervals, int[] newInterval) { // 用于存储最终结果的列表，因为最终结果的长度不确定，所以使用动态数组 ArrayList List<int[]> result = new ArrayList<>(); // 标记新的区间是否已经被添加到结果列表中 boolean added = false; // 用于遍历原区间数组的索引 int i = 0; // 原区间数组的长度 int n = intervals.length; // 开始遍历原区间数组 while (i < n) { // 获取当前遍历到的区间 int[] interval = intervals[i]; // 情况 1：当前区间在新插入区间的左侧，没有重叠 if (interval[1] < newInterval[0]) { // 直接将当前区间添加到结果列表中 result.add(interval); // 移动到下一个区间 i++; } // 情况 2：当前区间在新插入区间的右侧，没有重叠 else if (interval[0] > newInterval[1]) { // 如果新的区间还未添加到结果列表中，则先添加新的区间 if (!added) { result.add(newInterval); // 标记新的区间已添加 added = true; } // 将当前区间添加到结果列表中 result.add(interval); // 移动到下一个区间 i++; // 由于后续的区间都在新插入区间的右侧，直接将剩余的所有区间添加到结果列表中 while (i < n) { result.add(intervals[i]); i++; } } // 情况 3：当前区间与新插入区间有重叠 else { // 合并当前区间和新插入区间，更新新插入区间的起始位置为两者起始位置的最小值 newInterval[0] = Math.min(newInterval[0], interval[0]); // 更新新插入区间的结束位置为两者结束位置的最大值 newInterval[1] = Math.max(newInterval[1], interval[1]); // 移动到下一个区间 i++; } } // 处理所有区间都被合并的情况或原区间数组为空的情况 // 如果新的区间还未添加到结果列表中，则将其添加进去 if (!added) { result.add(newInterval); } // 将存储结果的列表转换为二维数组并返回 return result.toArray(new int[result.size()][]); } }

435. 无重叠区间

给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。

注意 只在一点上接触的区间是 不重叠的。例如 [1, 2] 和 [2, 3] 是不重叠的。

import java.util.Arrays; import java.util.Comparator; class Solution { /** * 该方法用于计算为了使给定的区间数组中的区间互不重叠，需要移除的区间的最小数量。 * * @param intervals 一个二维数组，其中每个一维数组表示一个区间，一维数组的长度为 2， * 分别代表区间的起始位置和结束位置。 * @return 为使区间互不重叠需要移除的区间的最小数量。 */ public int eraseOverlapIntervals(int[][] intervals) { // 首先对区间数组按照每个区间的结束位置进行升序排序 // 使用匿名内部类实现 Comparator 接口，重写 compare 方法来定义排序规则 // 这里通过 p[1] - q[1] 确保结束位置小的区间排在前面 Arrays.sort(intervals, new Comparator<int[]>() { @Override public int compare(int[] p, int[] q) { return p[1] - q[1]; } }); // 初始化变量 right 为排序后第一个区间的结束位置 // 用于记录当前已选择区间的最右边界 int right = intervals[0][1]; // 初始化变量 count 为 0，用于记录需要移除的区间数量 int count = 0; // 从第二个区间开始遍历排序后的区间数组 for (int i = 1; i < intervals.length; i++) { // 如果当前区间的起始位置小于已选择区间的最右边界 // 说明当前区间与已选择的区间重叠 if (intervals[i][0] < right) { // 由于要使区间互不重叠，所以需要移除当前重叠的区间 // 因此移除区间的数量加 1 count++; } else { // 如果当前区间与已选择的区间不重叠 // 则更新已选择区间的最右边界为当前区间的结束位置 right = intervals[i][1]; } } // 返回需要移除的区间的最小数量 return count; } } 9. 变形二分查找（Modified Binary Search）

变形二分查找是在基本二分查找的基础上，根据具体问题的需求对查找条件和边界处理进行调整，以解决一些更复杂的查找问题，例如在旋转排序数组中查找元素。

在处理涉及排序或旋转数组，且需要查找特定元素的问题时，可使用该模式。

示例问题： 在一个旋转排序数组中查找元素。

示例： 输入：nums = [4, 5, 6, 7, 0, 1, 2]，target = 0 输出：4 解释： 进行二分查找时，额外增加一个判断，以确定数组的哪一半是有序的。 然后检查目标元素是否在有序的那一半范围内。 如果在，就在这一半中查找；否则，在另一半中查找。

力扣相关题目：

33. 搜索旋转排序数组

整数数组 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) 的算法解决此问题。

class Solution { /** * 在旋转排序数组中搜索目标值。旋转排序数组是指一个原本有序的数组在某个点上进行了旋转， * 例如 [0,1,2,4,5,6,7] 旋转后可能变为 [4,5,6,7,0,1,2]。 * * @param nums 旋转排序数组 * @param target 要搜索的目标值 * @return 若目标值存在于数组中，返回其索引；否则返回 -1 */ public int search(int[] nums, int target) { // 初始化左指针，指向数组的起始位置 int left = 0; // 初始化右指针，指向数组的末尾位置 int right = nums.length - 1; // 当左指针小于右指针时，持续进行二分查找 while (left < right) { // 计算中间位置的索引 int mid = (left + right) / 2; // 如果中间位置的元素等于目标值，直接返回中间位置的索引 if (nums[mid] == target) return mid; // 判断左半部分是否有序 if (nums[left] <= nums[mid]) { // 如果目标值在左半部分的有序区间内 if (target >= nums[left] && target < nums[mid]) { // 缩小右边界，在左半部分继续查找 right = mid - 1; } else { // 目标值不在左半部分的有序区间内，缩小左边界，在右半部分查找 left = mid + 1; } } else { // 左半部分无序，说明右半部分有序 // 如果目标值在右半部分的有序区间内 if (target > nums[mid] && target <= nums[right]) { // 缩小左边界，在右半部分继续查找 left = mid + 1; } else { // 目标值不在右半部分的有序区间内，缩小右边界，在左半部分查找 right = mid - 1; } } } // 当 left 和 right 相遇时，检查该位置的元素是否等于目标值 if (nums[left] == target) return left; // 若不相等，说明目标值不在数组中，返回 -1 else return -1; } }

153. 寻找旋转排序数组中的最小值

已知一个长度为 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) 的算法解决此问题。

class Solution { /** * 该方法用于在旋转排序数组中查找最小值。旋转排序数组是指一个原本有序的数组在某个点上进行了旋转， * 例如 [0,1,2,4,5,6,7] 旋转后可能变为 [4,5,6,7,0,1,2]。 * * @param nums 旋转排序数组 * @return 数组中的最小值 */ public int findMin(int[] nums) { // 二分查找的区间定义说明： // 这里将二分区间设置为 [0, n - 2]，使用循环不变量来辅助查找。 // 循环不变量为：l - 1 位置代表最小值左边的元素，r + 1 位置代表最小值或者最小值右边的元素。 // 通过不断调整 l 和 r 的位置，最终让 l 指向最小值的位置。 // 获取数组的长度 int n = nums.length; // 初始化左指针 l 为 0，右指针 r 为 n - 2 // 因为二分区间为 [0, n - 2] int l = 0, r = n - 2; // 开始二分查找，当左指针小于等于右指针时，继续循环 while (l <= r) { // 计算中间位置的索引，使用 l + (r - l) / 2 避免 (l + r) 可能导致的整数溢出问题 int mid = l + (r - l) / 2; // 将中间位置的元素 nums[mid] 与数组最后一个元素 nums[n - 1] 进行比较 if (nums[mid] < nums[n - 1]) { // 如果 nums[mid] 小于 nums[n - 1]，说明最小值在 mid 及其左边 // 因此更新右指针 r 为 mid - 1，缩小查找范围到左半部分 r = mid - 1; } else { // 如果 nums[mid] 大于等于 nums[n - 1]，说明最小值在 mid 的右边 // 因此更新左指针 l 为 mid + 1，缩小查找范围到右半部分 l = mid + 1; } } // 当循环结束时，l 指向的就是最小值的位置 // 返回该位置的元素 return nums[l]; } }

240. 搜索二维矩阵 II

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

每行的元素从左到右升序排列。每列的元素从上到下升序排列。

class Solution { /** * 该方法用于在一个特殊的二维矩阵中查找目标值。这个二维矩阵具有以下特性： * 每行元素从左到右递增排序，每列元素从上到下递增排序。 * * @param matrix 给定的二维矩阵 * @param target 要查找的目标值 * @return 如果矩阵中存在目标值，返回 true；否则返回 false */ public boolean searchMatrix(int[][] matrix, int target) { // 获取矩阵的行数 int n = matrix.length; // 如果矩阵的行数为 0，说明矩阵为空，直接返回 false if (n == 0) return false; // 获取矩阵的列数 int m = matrix[0].length; // 从矩阵的右上角开始查找，初始化行索引 i 为 0，列索引 j 为最后一列的索引 for (int i = 0, j = m - 1; i < n && j >= 0;) { // 如果当前位置的元素等于目标值，说明找到了目标值，返回 true if (matrix[i][j] == target) return true; // 如果当前位置的元素大于目标值，由于每列元素从上到下递增， // 所以目标值不可能在当前列的下方，向左移动一列继续查找 if (matrix[i][j] > target) j--; // 如果当前位置的元素小于目标值，由于每行元素从左到右递增， // 所以目标值不可能在当前行的左边，向下移动一行继续查找 else i++; } // 遍历完整个矩阵都没有找到目标值，返回 false return false; } }