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

聰明

幫內推

大師，求carry

大師

大師