LETCODE 658. Find K Closest Elements

傷城~ 2021-09-26 20:00 212阅读 0赞

【658】 Find K Closest Elements  
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.由于数组是有序的，因此，首先比较第一个值与x的大小，如果x<=arr\[0\],则取前k个数。  
2.其次，比较最后一个值与x的大小，如果x>=arr\[length-1\],则取最后k个数。  
3.如果x的在最大值和最小值之间，则计算每个元素与x的差值，并保存差值d的个数。然后遍历差值个数的数组，找到x可以与数组元素的最大差值，依次遍历，将小于最大差值的元素添加到list中

public List<Integer> findClosestElements(int[] arr, int k, int x) {
            List<Integer> list = new ArrayList<Integer>();
            int index = 0;
            int length = arr.length;
            if( x <= arr[0]){
                index = 0;
                while(index<k){
                    list.add(arr[index++]);
                }
            }else if( x >= arr[length-1]){
                index = length-k;
                while(index<length){
                    list.add(arr[index++]);
                }
            }else{
                int[] temp = new int[length];
                int max = Math.max(x-arr[0], arr[length-1]-x);
                int[] counts = new int[max+1];
                for(int i = 0;i<length;i++){
                    temp[i] = Math.abs(arr[i]-x);
                    counts[temp[i]]++;
                }
                int total = 0;
                index = 0;
                int max_count = 0;
                int max_dis = 0;
                while(index<counts.length&&total<k){
                    if(total+counts[index]<k){
                        total += counts[index];
                        index++;
                    }else{                  
                        max_count = k - total;
                        max_dis = index;
                        break;
                    }
                }
                for(int i = 0;i<length;i++){
                    if(temp[i]<max_dis){
                        list.add(arr[i]);
                    }else if(temp[i] == max_dis){
                        if(max_count>0){
                            list.add(arr[i]);
                            max_count--;
                        }
                    }
                }
            }
            return list;
        }