Re: [閒聊] 每日leetcode
※ 引述《Rushia (早瀬ユウカの体操服 )》之銘言：
: https://leetcode.com/problems/find-k-th-smallest-pair-distance/description
: 719. Find K-th Smallest Pair Distance
首先觀察到 答案是與位置無關的
也就是任意兩個元素互換之後結果還是一樣的
所以可以假設是排序過的了
一旦假設是排序過的 就能發現可以用 binary search + sliding window 做
找出最小的 r 使得差距 <=r 的 pair 數 >= k 就是答案了
```
class Solution {
public:
int smallestDistancePair(vector<int>& nums, int k) {
int n = nums.size();
sort(nums.begin(), nums.end());
auto pred = [&](int r) {
// #[(i,j)<=r] >= k
int start = 0, total = 0;
for (int end = 0; end < n; end++) {
while (start < end && nums[end] - nums[start] > r)
start += 1;
total += end - start;
}
return total >= k;
};
int low = 0, high = 1e7;
while (low < high) {
int mid = low + (high - low) / 2;
if (pred(mid)) high = mid;
else low = mid + 1;
}
return low;
}
};
```
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 203.77.61.242 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1723601278.A.EE0.html
→
08/14 10:16,
1年前
, 1F
08/14 10:16, 1F
推
08/14 10:21,
1年前
, 2F
08/14 10:21, 2F
→
08/14 10:22,
1年前
, 3F
08/14 10:22, 3F
推
08/14 10:24,
1年前
, 4F
08/14 10:24, 4F
→
08/14 10:32,
1年前
, 5F
08/14 10:32, 5F
推
08/14 10:35,
1年前
, 6F
08/14 10:35, 6F
推
08/14 10:55,
1年前
, 7F
08/14 10:55, 7F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 709 之 1548 篇)：