Re: [閒聊] 每日LeetCode已回收

看板Marginalman作者Rushia (みけねこ的鼻屎)時間3年前 (2022/09/29 10:22)推噓4(4推 0噓 1→)

留言5則, 5人參與討論串16/719 (看更多)

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