Re: [閒聊] 每日leetcode
https://leetcode.com/problems/find-k-th-smallest-pair-distance/description
719. Find K-th Smallest Pair Distance
給你一個陣列 nums 和一個數字k 求出差的絕對值第k小的 pair 差是多少。
思路:
1.因為測資小又沒負數所以把所有pair絕對值算出來之後 counting 找出第k小就好。
java code
--------------------------------------------
class Solution {
public int smallestDistancePair(int[] nums, int k) {
int[] cnt = new int[1000001];
int n = nums.length;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
cnt[Math.abs(nums[i] - nums[j])]++;
}
}
int l = 0;
while (true) {
if (cnt[l++] == 0) {
continue;
}
k -= cnt[l - 1];
if (k <= 0) {
return l - 1;
}
}
}
}
--------------------------------------------
只有10% 感覺要 binary search 或 greedy 之類 = =
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 39.12.105.92 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1723600341.A.9FA.html
推
08/14 09:55,
1年前
, 1F
08/14 09:55, 1F
推
08/14 09:56,
1年前
, 2F
08/14 09:56, 2F
推
08/14 09:58,
1年前
, 3F
08/14 09:58, 3F
推
08/14 09:59,
1年前
, 4F
08/14 09:59, 4F
→
08/14 09:59,
1年前
, 5F
08/14 09:59, 5F
※ 編輯: Rushia (39.12.105.92 臺灣), 08/14/2024 12:09:18
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 708 之 1548 篇)：