k and an integer array A sorted in ascending order, find the k closest numbers to target in A, sorted in ascending order by the difference between the number and target. Otherwise, sorted in ascending order by number if the difference is same.1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 | public class Solution { /** * @param A an integer array * @param target an integer * @param k a non-negative integer * @return an integer array */ public int[] kClosestNumbers(int[] A, int target, int k) { // Write your code here int len = A.length; int j = closestNumber(A, target), i = j - 1, di, dj; int[] list = new int[Math.min(k, A.length)]; int count = 0; while(len-- != 0 && k-- != 0){ di = i < 0 ? Integer.MAX_VALUE : A[i] - target; dj = j >= A.length ? Integer.MAX_VALUE : A[j] - target; if(dj == 0 || Math.abs(dj) < Math.abs(di)){ list[count++] = A[j++]; } else{ list[count++] = A[i--]; } } return list; } private int closestNumber(int[] A, int target) { // Write your code here if(A == null || A.length == 0) return -1; int left = 0, right = A.length - 1, mid; while(left < right){ mid = left + (right - left) / 2; if(A[mid] < target){ left = mid + 1; } else{ right = mid; } } // when left == right, this is the first position that target can be insert if(right > 0 && (A[right] - target) > (target - A[right - 1])) return right - 1; else return right; }} |
K Closest Numbers In Sorted Array
原文：http://www.cnblogs.com/zhxshseu/p/6d73de551273e9171e220ae857517755.html