Given a sorted array, two integers k and x, find the k closest elements to x in the array. The result should also be sorted in ascending order. If there is a tie, the smaller elements are always preferred.
Example 1:
Example 2:
Note:
The value k is positive and will always be smaller than the length of the sorted array.
Length of the given array is positive and will not exceed 104
Absolute value of elements in the array and x will not exceed 104
這道題給我們了一個數組，還有兩個變量k和x。讓我們找數組中離x最近的k個元素，而且說明了數組是有序的，如果兩個數字距離x相等的話，取較小的那個。從給定的例子可以分析出x不一定是數組中的數字，我們想，由于數組是有序的，是以最後傳回的k個元素也一定是有序的，那麼其實就是傳回了原數組的一個長度為k的子數組，轉化一下，實際上相當于在長度為n的數組中去掉n-k個數字，而且去掉的順序肯定是從兩頭開始去，應為距離x最遠的數字肯定在首尾出現。那麼問題就變的明朗了，我們每次比較首尾兩個數字跟x的距離，将距離大的那個數字删除，直到剩餘的數組長度為k為止，參見代碼如下：
解法一：
<a>class Solution {</a>
下面這種解法是論壇上的高分解法，用到了二分搜尋法。其實部落客最開始用的方法并不是文章中的這兩個方法，雖然也是用的二分搜尋法，但部落客搜的是第一個不小于x的數，然後同時向左右兩個方向周遊，每次取和x距離最小的數加入結果res中，直到取滿k個為止。但是下面這種方法更加巧妙一些，二分法的判定條件做了一些改變，就可以直接找到要傳回的k的數字的子數組的起始位置，感覺非常的神奇。每次比較的是mid位置和x的距離跟mid+k跟x的距離，以這兩者的大小關系來确定二分法折半的方向，最後找到最近距離子數組的起始位置，參見代碼如下：
解法二：
參考資料：
<a href="https://discuss.leetcode.com/topic/99274/very-simple-and-short-acc-solution-modifying-the-input-list">https://discuss.leetcode.com/topic/99274/very-simple-and-short-acc-solution-modifying-the-input-list</a>
，如需轉載請自行聯系原部落客。