Re: [閒聊] 每日leetcode

[Rushia (早瀬ユウカの体操服 )]

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
推 JerryChungYC: 全算了 TLE了 :(
推 CanIndulgeMe: 技術大神
推 sustainer123: 能暴力解喔 下午試試
推 DJYOMIYAHINA: 我知道用binary search 但我還沒想到怎麼搜== 晚上
→ DJYOMIYAHINA: 回家想
※ 編輯: Rushia (39.12.105.92 臺灣), 08/14/2024 12:09:18