Given a target integer T, a non-negative integer K and an integer array A sorted in ascending order, find the K closest numbers to T in A.
Assumptions
A is not null
K is guranteed to be >= 0 and K is guranteed to be <= A.length
Return
A size K integer array containing the K closest numbers(not indices) in A, sorted in ascending order by the difference between the number and T.
Examples
A = {1, 2, 3}, T = 2, K = 3, return {2, 1, 3} or {2, 3, 1}
A = {1, 4, 6, 8}, T = 3, K = 3, return {4, 1, 6}
1 public class Solution {
2 public int[] kClosest(int[] array, int target, int k) {
3 // Write your solution here
4 //corner case
5 if (array == null || array.length < k) {
6 return array ;
7 }
8 //left is the index of the largest smaller or equal element
9 //right = left +1
10 //those two should be the closest to target
11 int left = largestSmallerEqual(array, target);
12 int right = left + 1 ;
13 int[] res = new int[k] ;
14 for (int i = 0 ; i < k ; i++ ) {
15 if (left >=0 && right < array.length){
16 if ((target - array[left]) <= (array[right] - target) ) {
17 res[i] = array[left--] ;
18 } else {
19 res[i] = array[right++] ;
20 }
21 } else if(left >=0 ){
22 res[i] = array[left--] ;
23 } else {
24 res[i] = array[right++] ;
25 }
26 }
27 return res ;
28 }
29 private int largestSmallerEqual(int[] array, int target){
30 int left = 0 , right = array.length - 1 ;
31 while(left + 1 < right){
32 int mid = left + (right - left)/2 ;
33 if(array[mid] <= target){
34 left = mid ;
35 } else {
36 right = mid ;
37 }
38 }
39 //post processing: 对最后跳的一次需要一个处理，选largest
40 if (array[right] <= target) {
41 return right ;
42 }
43 if (array[left] <= target) {
44 return left ;
45 }
46 return -1 ;
47 }
48 }