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:
Input: [1,2,3,4,5], k=4, x=3 Output: [1,2,3,4]
Example 2:
Input: [1,2,3,4,5], k=4, x=-1 Output: [1,2,3,4]
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
1 public class Solution { 2 public IList<int> FindClosestElements(int[] arr, int k, int x) { 3 var result = new List<int>(); 4 5 if (arr == null || arr.Length == 0 || k <= 0) return result; 6 7 if (k >= arr.Length) return arr.ToList(); 8 9 var index = FindIndex(arr, x); 10 11 int i = index - 1, j = index; 12 13 while (k > 0) 14 { 15 if ((i >= 0 && i < arr.Length) && (j >= 0 && j < arr.Length)) 16 { 17 var d1 = Math.Abs(x - arr[i]); 18 var d2 = Math.Abs(x - arr[j]); 19 20 if (d1 <= d2) 21 { 22 result.Add(arr[i]); 23 i--; 24 } 25 else 26 { 27 result.Add(arr[j]); 28 j++; 29 } 30 } 31 else if (i >= 0 && i < arr.Length) 32 { 33 result.Add(arr[i]); 34 i--; 35 } 36 else if (j >= 0 && j < arr.Length) 37 { 38 result.Add(arr[j]); 39 j++; 40 } 41 42 k--; 43 } 44 45 result.Sort(); 46 47 return result; 48 } 49 50 private int FindIndex(int[] arr, int x) 51 { 52 int low = 0, high = arr.Length; 53 54 while (low < high) 55 { 56 int mid = low + (high - low) / 2; 57 58 if (arr[mid] == x) 59 { 60 return mid; 61 } 62 else if (arr[mid] < x) 63 { 64 low = mid + 1; 65 } 66 else 67 { 68 high = mid; 69 } 70 } 71 72 return low; 73 } 74 }