当前位置：首页 > news >正文

每日算法-250410

news 来源：原创 2025/9/15 1:37:20

今天分享两道 LeetCode 题目，它们都可以巧妙地利用二分查找来解决。

275. H 指数 II

问题描述

H 指数 II 题目描述

思路：二分查找

H 指数的定义是：一个科学家有 h 篇论文分别被引用了至少 h 次。
题目给定的 citations 数组是升序排列的。这为我们使用二分查找提供了可能。

我们可以尝试猜测一个 H 指数 h，然后检查是否满足条件。如果 citations 数组中存在 h 篇论文的引用次数都大于等于 h，那么这个 h 就是一个可能的 H 指数。我们希望找到最大的那个 h。

考虑数组下标 mid 和数组长度 n。
如果 citations[mid] 表示第 mid 篇论文的引用次数（数组从0开始计数），那么从 mid 到 n-1 一共有 n - mid 篇论文。
由于数组是升序的，这 n - mid 篇论文的引用次数都至少为 citations[mid]。

我们的目标是找到一个最大的 h，使得有 h 篇论文的引用次数至少为 h。
这可以转化为：找到一个最大的 h，使得 citations[n-h] >= h。

解题过程：二分查找 H 指数的边界

我们可以利用二分查找来寻找这个 h 的临界点。
搜索范围是 [0, n] (可能的h指数范围)，但更方便的是直接在数组下标 [0, n-1] 上进行二分。

二分条件：比较 citations[mid] 和 n - mid。
- n - mid 代表的是：如果我们假设 H 指数是 h = n - mid，那么我们需要 n - mid 篇论文的引用次数至少为 n - mid。
- 由于数组已排序，从下标 mid 到 n-1 的这 n - mid 篇论文是引用次数最高的。
- citations[mid] 是这 n - mid 篇论文中引用次数最少的那一篇。
- 因此，判断条件 citations[mid] >= n - mid 意味着：以 mid 为起点的这 n - mid 篇论文，它们的引用次数都至少为 n - mid。这表明 h = n - mid 是一个可能的 H 指数。
指针移动：
- 如果 citations[mid] >= n - mid：说明当前的 mid 对应的 h = n - mid 是一个潜在的 H 指数。但是，我们想找最大的 h。更大的 h 对应着更小的数组下标。所以，我们尝试在左半部分 [left, mid - 1] 继续搜索，看看能否找到一个更小的 mid' 使得 citations[mid'] >= n - mid' 成立（这意味着更大的 h）。因此，right = mid - 1。
- 如果 citations[mid] < n - mid：说明当前的 mid 对应的 h = n - mid 太大了，连引用次数最少的 citations[mid] 都达不到 n - mid 次。我们需要减小 h，也就是增大 mid。所以，在右半部分 [mid + 1, right] 搜索。因此，left = mid + 1。
结果：
- 循环结束时 (left > right)，left 指向的是第一个不满足 citations[mid] >= n - mid 条件的 mid 的下一个位置（或者说是第一个满足 citations[mid] < n - mid 的位置，如果我们是从左往右看的话）。
- 根据 H 指数的定义，满足 citations[i] >= n - i 的下标 i 越小，对应的 h = n - i 就越大。
- left 是第一个使得 h = n - left 不再满足条件（或刚好满足条件的边界的下一个）的下标。
- 那么，最大的满足条件的 h 就是 n - left。因为从 left 到 n-1 一共有 n - left 个元素，而 left 是使得 citations[left] >= n - left 潜在成立的最小下标（或者说，left-1 是最后一个明确满足 citations[right] >= n - right 的 right 值之后的位置）。因此，有 n - left 篇论文（下标从 left 到 n-1）的引用次数大于等于 n - left。

复杂度

时间复杂度: $O(\log n)$ , 因为使用了二分查找。
空间复杂度: $O (1)$ , 只使用了常数级别的额外空间。

Code

class Solution {public int hIndex(int[] citations) {int n = citations.length;int left = 0, right = n - 1;while (left <= right) {int mid = left + (right - left) / 2;if (citations[mid] >= n - mid) {right = mid - 1;} else {left = mid + 1;}}return n - left;}
}

2226. 每个小孩最多能分到多少糖果

问题描述

每个小孩最多能分到多少糖果题目描述

思路：二分查找

这个问题的核心在于找到一个最大的糖果数 x，使得我们可以从 candies 数组中分割出至少 k 堆，每堆都包含 x 个糖果。

我们可以观察到这个问题的答案具有单调性：

如果我们能让每个小孩分到 x 个糖果，那么我们肯定也能让每个小孩分到 x-1 个糖果。
如果我们无法让每个小孩分到 x 个糖果，那么我们肯定也无法让每个小孩分到 x+1 个糖果。

这种单调性非常适合使用二分查找来解决。我们可以在可能的糖果数范围 [1, max_candies] 内进行二分查找。

解题过程：二分答案

确定搜索范围：
- 每个小孩至少分到 1 个糖果（如果可能的话），所以下界 left = 1。
- 每个小孩最多能分到的糖果数不会超过 candies 数组中的最大值 max(candies[i])，也不会超过总糖果数除以小孩数 sum(candies) / k。所以上界 right 可以取 min(max(candies[i]), sum(candies) / k)。需要注意，如果 sum < k，则一个都分不了，应返回 0。我们在计算 right 时处理这种情况。
- 注意：糖果总数 sum 和小孩数 k 可能很大，需要使用 long 类型。
check(mid) 函数：我们需要一个辅助函数 check(candies, mid, k) 来判断：如果每个小孩分 mid 个糖果，是否能够满足 k 个小孩的需求。
- 遍历 candies 数组中的每一堆糖果 c。
- 对于每一堆 c，它可以分出 c / mid 份，每份包含 mid 个糖果。
- 计算所有糖果堆能分出的总份数 count = sum(c / mid)。
- 判断逻辑：如果 count >= k，说明分 mid 个糖果是可行的。如果 count < k，说明分 mid 个糖果是不可行的。
二分查找逻辑：
- 计算中间值 mid = left + (right - left) / 2。
- 调用 check(candies, mid, k)。
- 指针移动：
  - 如果 check 返回 true（即 count >= k），说明每个小孩分 mid 个糖果是可行的。我们希望找到最大的可行值，所以我们尝试增大 mid，在右半部分 [mid + 1, right] 继续搜索，并记录 mid 作为一个可能的答案。ans = mid; left = mid + 1;
  - 如果 check 返回 false（即 count < k），说明每个小孩分 mid 个糖果是不可行的，mid 太大了。我们需要减小 mid，在左半部分 [left, mid - 1] 搜索。right = mid - 1;
结果：
- 我们可以维护一个变量 ans 来记录最后一次 check 成功的 mid 值。当循环结束时，ans 就是最大可行解。
- 循环结束后，right 指向的就是最大的可行解。为什么？因为 right 最终停在最后一个使得 check 成功的 mid 上（或者是 mid-1 移动过来的）。当 left 超过 right 时，left 指向第一个使得 check 失败的值，而 right 指向最后一个使得 check 成功的值。
- 代码细节：下面代码中的 check 函数返回的是 count < k（即是否不可行）。
  - if (check(candies, mid, k)) 为 true (即 count < k，不可行)，则 right = mid - 1 (需要减小糖果数)。
  - if (check(candies, mid, k)) 为 false (即 count >= k，可行)，则 left = mid + 1 (尝试增加糖果数)。
  - 循环结束后，left 是第一个使得 count < k 的 mid 值，right 是最后一个使得 count >= k 的 mid 值。因此返回 right。

复杂度

时间复杂度: $\log M)$ , 其中 N 是糖果堆的数量 (candies.length)，M 是糖果数的最大可能范围（即 right 的初始值）。每次 check 需要 $O (N)$ 时间，二分查找进行 $O(\log M)$ 次。
空间复杂度: $O (1)$ , 只使用了常数级别的额外空间。

Code

class Solution {public int maximumCandies(int[] candies, long k) {long sum = 0;int max = 0;for (int i = 0; i < candies.length; i++) {sum += candies[i];max = Math.max(max, candies[i]);}int left = 1, right = (int)Math.min(max, sum / k);if (right <= 0) {return 0;}while (left <= right) {int mid = left + (right - left) / 2;if (check(candies, mid, k)) {right = mid - 1;} else {left = mid + 1;}}return right;}private boolean check(int[] arr, int max, long k) {long count = 0;for (int i = 0; i < arr.length; i++) {count += arr[i] / max;}return count < k;}
}

问题描述

思路：二分查找

解题过程：二分查找 H 指数的边界

复杂度

Code

问题描述

思路：二分查找

解题过程：二分答案

复杂度

Code

相关文章：