記錄今天解決的兩道 LeetCode 算法題，主要涉及二分查找的應用。
1283. 使結果不超過閾值的最小除數
題目描述
思路
核心思路是 二分查找。
解題過程
-
為什么可以使用二分？
關鍵在于單調性。對于一個固定的數組nums，當除數divisor增大時，每個元素num / divisor(向上取整) 的值是 非遞增 的，因此它們的總和也是 非遞增 的。
我們要求的是滿足sum <= threshold的 最小divisor。- 如果當前除數
mid計算出的總和sum大于threshold，說明mid太小了，我們需要增大除數。因此，真正的答案一定在[mid + 1, right]區間。 - 如果當前除數
mid計算出的總和sum小于等于threshold，說明mid是一個可能的解，但可能存在更小的除數也滿足條件。因此，我們嘗試在[left, mid - 1]區間尋找更小的解，同時記錄mid作為潛在答案。
- 如果當前除數
-
二分查找的目標？
我們要查找的是滿足條件的 最小 正整數除數。 -
查找范圍？
left：最小可能的除數是 1（題目要求正整數除數）。right：最大可能的除數是多少？如果除數非常大（例如，等于數組中的最大元素），那么每個數除后的結果向上取整至少是 1，總和至少是nums.length。如果除數是數組中的最大值max(nums)，那么每個ceil(num / max(nums))都是 1，總和為nums.length。因此，一個合理的上界是數組中的最大元素值。如果閾值threshold非常小（比如等于nums.length），那么除數可能需要等于最大元素值。
-
check函數：
需要一個輔助函數check(nums, divisor)來計算在當前除數divisor下，數組元素的除法結果（向上取整）之和。計算ceil(x / divisor)可以用(x + divisor - 1) / divisor的整數除法實現，或者像原始代碼那樣判斷余數。
復雜度
- 時間復雜度: O(N log M)
- 其中 N 是數組
nums的長度。 - M 是二分查找的范圍上限，即
nums中的最大元素值。 - 每次
check函數需要 O(N) 的時間遍歷數組。 - 二分查找需要 O(log M) 次
check調用。
- 其中 N 是數組
- 空間復雜度: O(1)
- 我們只需要常數級別的額外空間來存儲
left,right,mid和sum等變量。
- 我們只需要常數級別的額外空間來存儲
Code
class Solution {public int smallestDivisor(int[] nums, int threshold) {Arrays.sort(nums);int left = 1, right = nums[nums.length - 1];while (left <= right) {int mid = left + (right - left) / 2;if (check(nums, mid) < threshold + 1) {right = mid - 1;} else {left = mid + 1;}}return left;}private int check(int[] nums, int divisor) {int sum = 0;for (int x : nums) {if (x % divisor == 0) {sum += x / divisor;} else {sum += x / divisor + 1;}}return sum;}
}
1170. 比較字符串最小字母出現頻次
題目描述
思路
結合 預處理 和 二分查找。
解題過程
-
計算頻率
f(s)：
首先，需要實現一個函數f(s)，用于計算給定字符串s中字典序最小的字符的出現次數。遍歷字符串，找到最小字符，并統計其出現次數。 -
預處理
words：
對words數組中的每個字符串W，計算其f(W)，并將這些頻率值存儲在一個新的整數數組wFreq中。 -
排序
wFreq：
為了能夠高效地查找滿足f(queries[i]) < f(W)的W的數量，我們將wFreq數組進行升序排序。 -
二分查找：
對于每個queries[i]:
a. 計算qVal = f(queries[i])。
b. 我們需要在已排序的wFreq數組中找到 第一個 大于qVal的元素的位置idx。
c.wFreq數組中從idx到末尾的所有元素都滿足f(W) > qVal。因此，滿足條件的W的數量就是wFreq.length - idx。
d. 查找 “第一個大于qVal的元素” 可以通過二分查找實現。具體地，我們可以查找 第一個大于等于qVal + 1的元素的位置。
復雜度
- 時間復雜度: O(Lq * N + Lw * M + M log M + N log M)
- 其中 N 是
queries的長度，M 是words的長度。 - Lq 和 Lw 分別是
queries和words中字符串的最大長度。 - 計算所有
f(queries[i])需要 O(Lq * N)。 - 計算所有
f(W)需要 O(Lw * M)。 - 對
wFreq排序需要 O(M log M)。 - 對每個
query進行二分查找需要 O(log M)，總共 N 次查找為 O(N log M)。 - 整體復雜度由這些部分相加決定。如果字符串長度較小，主要由排序和查找決定。
- 其中 N 是
- 空間復雜度: O(N + M)
- 需要 O(N) 空間存儲
queries的頻率結果（或者直接在結果數組中計算）。 - 需要 O(M) 空間存儲
words的頻率數組wFreq。 - 排序可能需要 O(log M) 或 O(M) 的額外棧空間或臨時空間，但 O(N+M) 通常是主導。
- 需要 O(N) 空間存儲
Code
import java.util.Arrays;class Solution {public int[] numSmallerByFrequency(String[] queries, String[] words) {int n = queries.length, m = words.length;int[] qFreq = new int[n]; // 存儲 queries 的 f 值int[] wFreq = new int[m]; // 存儲 words 的 f 值int[] ans = new int[n]; // 存儲最終結果// 1. 計算 queries 中每個字符串的 f 值for (int i = 0; i < n; i++) {qFreq[i] = calculateF(queries[i]);}// 2. 計算 words 中每個字符串的 f 值for (int i = 0; i < m; i++) {wFreq[i] = calculateF(words[i]);}// 3. 對 words 的頻率數組進行排序Arrays.sort(wFreq);// 4. 對每個 query 的頻率值，在排好序的 wFreq 中進行二分查找for (int i = 0; i < n; i++) {int targetFreq = qFreq[i];// 查找第一個嚴格大于 targetFreq 的元素的位置// 等價于查找第一個大于等于 targetFreq + 1 的元素的位置int index = findFirstGreater(wFreq, targetFreq);ans[i] = m - index; // 從該位置到數組末尾的元素個數即為所求}return ans;}// 計算字符串 s 的 f(s) 值private int calculateF(String s) {if (s == null || s.isEmpty()) {return 0;}char minChar = 'z' + 1; // 初始化為一個比 'z' 大的字符int count = 0;for (char c : s.toCharArray()) {if (c < minChar) {minChar = c;count = 1; // 找到了更小的字符，重置計數} else if (c == minChar) {count++; // 遇到了相同的最小字符，增加計數}}return count;}// 在升序數組 arr 中查找第一個嚴格大于 target 的元素的索引// 如果所有元素都小于等于 target，返回 arr.lengthprivate int findFirstGreater(int[] arr, int target) {int left = 0, right = arr.length - 1;int resultIndex = arr.length; // 默認為數組長度，表示沒找到while (left <= right) {int mid = left + (right - left) / 2;if (arr[mid] > target) {// arr[mid] 比 target 大，可能是第一個，也可能前面還有resultIndex = mid; // 記錄當前這個可能的位置right = mid - 1; // 繼續向左查找更小的索引} else {// arr[mid] 小于等于 target，需要向右查找更大的值left = mid + 1;}}return resultIndex;}
}
