719. 找出第 K 小的數對距離 - 力扣（LeetCode）

數對 (a,b) 由整數 a 和 b 組成，其數對距離定義為 a 和 b 的絕對差值。

給你一個整數數組 nums 和一個整數 k ，數對由 nums[i] 和 nums[j] 組成且滿足 0 <= i < j < nums.length 。返回 所有數對距離中 第 k 小的數對距離。

示例 1：

輸入：nums = [1,3,1], k = 1 輸出：0 解釋：數對和對應的距離如下： (1,3) -> 2 (1,1) -> 0 (3,1) -> 2 距離第 1 小的數對是 (1,1) ，距離為 0 。

示例 2：

輸入：nums = [1,1,1], k = 2 輸出：0

示例 3：

輸入：nums = [1,6,1], k = 3 輸出：5

提示：

• n == nums.length

• 2 <= n <= 10(4)

• 0 <= nums[i] <= 10(6)

• 1 <= k <= n * (n - 1) / 2

方法1,二分答案法,沒有剪枝

1.

nums數組中的數對組合,下標分別為<0,1>,<0,2>...<0,n-1>

<1,2>,<1,3>....<1,n-1>

....

<n-2,n-1>

一共有n-1+n-2+....+1=((n-1)+1)*(n-1)/2=(n-1)*n/2對數對.

對于每一個數對,差值的絕對值,可以發現排序之后不會影響數組組合和結果.

我們需要找到所有數對距離從大到小排序之后的第k小的數對距離.

2.

將所有的數對距離排序之后,找到第k小的數對距離.

我們需要找一個數對距離的值,這個值是第k小的數對距離.

如果固定數對距離,可以求得他是第幾小的數對距離,只需要求得小于等于limit的數對距離有多少個就知道這是第幾小的數對距離.

用二分法找數對距離,判斷數對距離是否是第k小的數對距離.

f(limit)函數返回小于等于limit數對距離的個數.如果小于k,說明數對距離不可能是答案.[0,limit]都不可能是答案.

去右邊找答案.

如果是大于等于k,說明可能是答案,ret記錄下來,去左邊找可能的答案.

class Solution {
public:/*數對距離,二元組,排序和不排序不影響答案.數組n個元素,對應的數對個數是1+2+...+n-1=(1+n-1)*(n-1)/2=n*(n-1)/2分別下標對應<0,1><0,2>...<0,n-1>====> n-1<1,2>...<1,n-1>=====> n-2...<n-2,n-1>=====> 1數對距離的可能范圍[0,num_max-nums_min]數對距離排序之后第k個,是我們要找的值數對距離排序后第k個數對距離是答案.二分答案法,f(limit)數對距離大于等于limit的個數.二分答案法,固定答案判斷其他條件,更方便1,2,3,4,5,6*/vector<int> arr; // 保存輸入的數組int k; // 第 k 小的數對距離int n; // 數組長度int ret; // 保存結果，即第 k 小的數對距離// 判斷在給定的限制下，數對距離小于等于 limit 的個數是否大于等于 kbool f(int limit) {int count = 0; // 滿足條件的數對個數for (int i = 0; i < n; i++) {for (int j = i + 1; j < n; j++) {if (arr[j] - arr[i] <= limit) {count++;} else {break;}}}return count >= k;}// 初始化函數，計算數組長度并排序void init() {n = 0, ret = 0;sort(arr.begin(), arr.end());n = arr.size();}// 二分查找解決問題void solve() {int l = 0, r = arr[n - 1] - arr[0]; // 定義二分查找的左右邊界while (l <= r) {int mid = l + ((r - l) >> 1); // 計算中間值if (f(mid)) { // 如果在當前限制下滿足條件的數對個數大于等于 kret = mid; // 更新結果r = mid - 1; // 縮小右邊界} else {l = mid + 1; // 增大左邊界}}}// 主函數，計算第 k 小的數對距離int smallestDistancePair(vector<int>& _nums, int _k) {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); // 加速輸入輸出arr = _nums, k = _k;init(); // 調用初始化函數solve(); // 調用二分查找解決問題return ret; // 返回結果}
};

方法2,二分答案法,剪枝

1.

找小于等于limit的個數是否大于等于k.

這個過程j可以不用回退.

i和i+1~j-1數對距離都小于等于limit,但是i和j數對距離大于limit,那么i+1和i+1~j-1的數對距離也以一定小于等于limit.

所以j不需要回退,直接加上當前位置和j之間的個數.

如果ij相等j需要++.

class Solution {
public:/*數對距離,二元組,排序和不排序不影響答案.數組n個元素,對應的數對個數是1+2+...+n-1=(1+n-1)*(n-1)/2=n*(n-1)/2分別下標對應<0,1><0,2>...<0,n-1>====> n-1<1,2>...<1,n-1>=====> n-2...<n-2,n-1>=====> 1數對距離的可能范圍[0,num_max-nums_min]數對距離排序之后第k個,是我們要找的值數對距離排序后第k個數對距離是答案.二分答案法,f(limit)數對距離大于等于limit的個數.二分答案法,固定答案判斷其他條件,更方便1,2,3,4,5,6*/vector<int> arr;int k;int n;int ret;bool f(int limit) {// 判斷在給定的限制下，數對距離小于等于 limit 的個數是否大于等于 kint count = 0;int j = 1;for (int i = 0; i < n; i++) {if (i == j)j++;count += j - i - 1;for (; j < n; j++) {//剪枝不回退if (arr[j] - arr[i] <= limit) {count++;} else {break;}}}return count >= k;}void init() {n = 0, ret = 0;sort(arr.begin(), arr.end());n = arr.size();}void solve() {int l = 0, r = arr[n - 1] - arr[0];while (l <= r) {int mid = l + ((r - l) >> 1);//位運算一定要加括號if (f(mid)) {ret = mid;r = mid - 1;} else {l = mid + 1;}}}int smallestDistancePair(vector<int>& _nums, int _k) {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);arr = _nums, k = _k;init();solve();return ret;}
};

N 臺電腦的最長時間 - 力扣（LeetCode）

你有 n 臺電腦。給你整數 n 和一個下標從 0 開始的整數數組 batteries ，其中第 i 個電池可以讓一臺電腦 運行 batteries[i] 分鐘。你想使用這些電池讓 全部 n 臺電腦 同時 運行。

一開始，你可以給每臺電腦連接 至多一個電池 。然后在任意整數時刻，你都可以將一臺電腦與它的電池斷開連接，并連接另一個電池，你可以進行這個操作 任意次 。新連接的電池可以是一個全新的電池，也可以是別的電腦用過的電池。斷開連接和連接新的電池不會花費任何時間。

注意，你不能給電池充電。

請你返回你可以讓 n 臺電腦同時運行的 最長 分鐘數。

示例 1：

輸入：n = 2, batteries = [3,3,3] 輸出：4 解釋： 一開始，將第一臺電腦與電池 0 連接，第二臺電腦與電池 1 連接。 2 分鐘后，將第二臺電腦與電池 1 斷開連接，并連接電池 2 。注意，電池 0 還可以供電 1 分鐘。 在第 3 分鐘結尾，你需要將第一臺電腦與電池 0 斷開連接，然后連接電池 1 。 在第 4 分鐘結尾，電池 1 也被耗盡，第一臺電腦無法繼續運行。 我們最多能同時讓兩臺電腦同時運行 4 分鐘，所以我們返回 4 。

示例 2：

輸入：n = 2, batteries = [1,1,1,1] 輸出：2 解釋： 一開始，將第一臺電腦與電池 0 連接，第二臺電腦與電池 2 連接。 一分鐘后，電池 0 和電池 2 同時耗盡，所以你需要將它們斷開連接，并將電池 1 和第一臺電腦連接，電池 3 和第二臺電腦連接。 1 分鐘后，電池 1 和電池 3 也耗盡了，所以兩臺電腦都無法繼續運行。 我們最多能讓兩臺電腦同時運行 2 分鐘，所以我們返回 2 。

提示：

• 1 <= n <= batteries.length <= 10(5)

• 1 <= batteries[i] <= 10(9)

1.

我們需要找運行時間,電池可以供電腦運行的最長的時間,我們找的這個時間一定有一個范圍,0~所有時間累加和/n.

我們希望運行時間盡可能長.

f函數表示limit某一個特定的運行時間,電池是否可以供這些電腦運行這些時間.

如果不能說明limit這個運行時間短了,如果可以,再去更大的運行時間找,看看有沒有更大的答案.

2.

f函數怎么判斷這些電池能否供電腦運行這些時間,電池的電量如果大于等于limit,這個電池直接供一個電腦就可以了,如果電池電量小于limit說明,這個電池供完之后還需要其他的電池的幫助,這就是一個電池累加和,和總需要的電量的匹配問題.

只需要保證這些電池的累加和大于等于我們需要的電量即可.

所以我們需要將電量小于limit的電量累加,電腦數減去電量大于等于limit的個數,這個數乘以limit.

看累加電量是否大于等于n*limit.

3.

可以統一操作,如果不對n這個數進行修改,還原回去,左邊就需要加上等量的值.也就是limit*(電量大于等于limit的個數).只需要電量大于等于limit的值加limit即可.

class Solution {
public:#define LL long long // 定義長整型別名int n; // 電腦的數量vector<int> arr; // 電池的電量數組LL ret; // 記錄最長運行時間LL sum; // 電池電量總和// 判斷在給定限制時間limit下，電池能否支持所有電腦運行bool f(LL limit) {LL totalTime = 0; // 記錄總共供電時間for (int i = 0; i < arr.size(); ++i) {// 如果電池電量大于等于限制時間，則加上限制時間；否則，加上電池電量totalTime += arr[i] >= limit ? limit : arr[i];// 如果總供電時間大于等于限制時間乘以電腦數量，返回trueif (totalTime >= limit * n) {return true;}}return false; // 如果無法滿足條件，返回false}// 初始化，計算電池電量總和void init() {sum = accumulate(arr.begin(), arr.end(), 0LL);}// 二分查找解決最長運行時間void solve() {LL l = 0, r = sum / n; // 左邊界為0，右邊界為電池總電量除以電腦數量while (l <= r) {LL mid = l + ((r - l) >> 1); // 計算中間值// 如果在中間值限制下可以滿足條件，更新結果，并嘗試更長時間if (f(mid)) {ret = mid;l = mid + 1;} else { // 否則，嘗試更短時間r = mid - 1;}}}// 主函數，計算最大運行時間long long maxRunTime(int _n, vector<int>& _batteries) {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); // 加速輸入輸出n = _n; // 初始化電腦數量arr = _batteries; // 初始化電池數組init(); // 計算電池總電量solve(); // 二分查找計算最大運行時間return ret; // 返回結果}
};

結尾

最后，感謝您閱讀我的文章，希望這些內容能夠對您有所啟發和幫助。如果您有任何問題或想要分享您的觀點，請隨時在評論區留言。

同時，不要忘記訂閱我的博客以獲取更多有趣的內容。在未來的文章中，我將繼續探討這個話題的不同方面，為您呈現更多深度和見解。

謝謝您的支持，期待與您在下一篇文章中再次相遇！?????????