Re: [閒聊] 每日LeetCode

[Rushia (みけねこ的鼻屎)]

658. Find K Closest Elements
說明：
給定一個排序好的陣列arr、一個數字k和一個數字x，我們需返回一個大小為k的列表，
其中的數字要是最接近x的數字，若數字一樣接近則數字小的優先，返回的列表必須也是
排序好的。

Example 1:
Input: arr = [1,2,3,4,5], k = 4, x = 3
Output: [1,2,3,4]


法一 Heap+暴力法

思路：
1.把所有數字都丟進min heap，絕對值小的排最前面，絕對值一樣則比較本身的值
2.從heap中取出k個值放入列表
3.排序列表

Java Code：
class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        List<Integer> res = new ArrayList<>();
        PriorityQueue<int[]> queue = new PriorityQueue<>((a,b) ->
                a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]
        );
        for (int n : arr)
            queue.offer(new int[]{Math.abs(x - n), n});
        for(int i = 0; i < k; i++)
            res.add(queue.poll()[1]);
        res.sort(Comparator.naturalOrder());
        return res;
    }
}

時間複雜度：O(nlogn + k + klogk)

法二 雙指標

思路：
1.取出k個最接近的數之問題等同於從原陣列刪除 n - k個數，又對於某數x來說距離
最遠的數只能是最左邊的數或最右邊的數。
2.比較陣列的最左和最右元素，維護兩個指標，指標不交集的範圍表示被刪除，每次都
刪除絕對值較大的，若相等則優先刪除右邊。
3.把指標start到end範圍的數存入List返回。

Java Code：
class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        List<Integer> res = new ArrayList<>();
        int n = arr.length, start = 0, end = n - 1;
        for(int i = 0; i < n - k; i++) {
            int diff1 = Math.abs(x - arr[start]);
            int diff2 = Math.abs(x - arr[end]);
            if(diff1 > diff2) start++;
            else end--;
        }
        for(int i = start; i <= end; i++)
            res.add(arr[i]);
        return res;
    }
}

時間複雜度：O(n)

--
https://i.imgur.com/uiFto42.jpg

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.231.4.240 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1664418163.A.D06.html
推 Ericz7000: 聰明
※ 編輯: Rushia (36.231.4.240 臺灣), 09/29/2022 10:26:47
→ Rushia: 幫內推
推 KusanagiYuma: 大師，求carry
推 pandix: 大師
※ 編輯: Rushia (36.231.4.240 臺灣), 09/29/2022 10:52:06
推 JerryChungYC: 大師