Leetcode 658) Find K Closest Elements

17 Sep 2021 in Algorithms

My solution

• 와아아 이게 될줄 몰랐는데.. 이게 되네..? 후후후 생각하고 풀었는데 한번에 맞아서 기분이 넘 좋다

class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        List<Integer> res = new ArrayList<>();
        
        //finding x by binary search
        //I want every elements to be examined
        int left =0;
        int right=arr.length-1;
        //while 조건문 할 때, right 를 뭘 줘야하는지 생각하면 된다! 글구 원소 한 개일때, 두개일때.. 한개일때도 돌아감! 그게 내가 원헀던 것.
        //left <= right 해놓고, arr.length 하면, 원소가 한개인데 두번이나 돌아간다.? =>아니네, 이것도 right 값 어떻게 갱신하느냐에 따라 다르긴하네 
        //아 이거를 알아서 유도리있게 조절하면 되는거구나..
        // left <right 하고, arr.length 하면, 원소가 한개일 때 한번 돌아가지만,
        //i want all elements to be examined.
        int target=-1;
        while(left<=right){
            int mid = left +(right-left)/2;
            if(arr[mid]==x){
                target=mid;
                break;
            }else if(arr[mid]>x){
                right= mid-1;
            }else{
                left=mid+1;
            }
        }
        //there are 2 possibilities of getting out while loop, 
        //1 ) mid existed. 
        int cnt = 0;
        //둘이 교차하면서 끝날거니까
        int lptr= right;
        int rptr= left;
        if(target!=-1){
            res.add(x);
            lptr= target-1;
            rptr= target+1;
            cnt++;
        }
        
        while(cnt < k){
                //when lptr and r ptr is in the range
            if(lptr>=0 &&  rptr<arr.length){
                if(x-arr[lptr]<=arr[rptr]-x){
                    // res should be 
                    res.add(0,arr[lptr]); 
                    lptr--;
                }else{
                    res.add(arr[rptr]);
                    rptr++;
                }
                cnt++;
            }else if(lptr<0){
                while(cnt<k){
                    res.add(arr[rptr]);
                    rptr++;
                    cnt++;
                }
            }else if(rptr>=arr.length){
                res.add(0,arr[lptr]);
                lptr--;
                cnt++;
            }
        }
        return res;
    }
}

Other Answer

class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        
        int low = 0;
        int high = arr.length - k;
        
        while (low < high) {
            int mid = low + (high - low) / 2;
            
            if (x <= arr[mid]) {
                high = mid;
            }
            
            else if (x >= arr[mid+k]) {
                low = mid + 1;
            }
            
            // x lies between mid and mid+k... excluding boundary... find closer distance
            else {
                if (Math.abs(x - arr[mid]) <= Math.abs(x - arr[mid+k])) {
                    high = mid;
                }
                else {
                    low = mid + 1;
                }
            }
        }     
        // return subarray
        List<Integer> res = new ArrayList(k);
        for (int i = 0; i < k; i++) {
            res.add(arr[low + i]);
        }
        return res;
    }
}