Find K Closest Elements


  • 0

    Click here to see the full article post


  • 0

    What is "binary sort"? And what makes you think the sorting doesn't consume extra space?


  • 1
    S

    Note that space complexity of a.subList may be O(1) because subList is done in-place when supported by the implementation, returning a "view" over the original list, as explained in the List interface spec. For example, if you look at the ArrayList implementation and its SubList private class.


  • 0

    @sagimann Oh, excellent. Didn't know it returns a view. Means my Java solution was probably already O(log n) :-). Wrote a bit about subList there now.


  • 0
    K
    class Solution {
    public:
    	vector<int> findClosestElements(vector<int>& arr, int k, int x) {
    		auto h = arr.size() - k;
    		auto l = 0;
    		while (l < h) {
    			auto mid = (l + h) / 2;
    			if (abs(arr[mid] - x) <= abs(arr[k + mid] - x)) {
    				h = mid;
    			}
    			else {
    				l = mid + 1;
    			}
    		}
    		vector<int> rst(arr.begin() + h, arr.begin() + h + k);
    		return rst;
    	}
    };
    

    I think my solution is O(log(n)) in search phase


  • 0
    A

    Question for the second method, how could you know whether the input List is inputed by ArrayList or LinkedList? If it is the latter, then the binarySearch operation and get(index) operation will cost not only O(1) time.


  • 1

    @Albert_G The problem says "array" five times. And the variable is called arr. I think it's fair to assume that it's an array.


  • 0
    B

    wtf this binary search?


  • 0
    A

    In the second solution, I don't understand why low < 0 and high > arr.size() - 1 conditions are required. Also the unhandled case is never reachable.


  • 0

    Collections.sort()

    There is some compile error with the first sort solution. Anyway, the idea is neat. The following is an implementation using Java 8 stream.

    class Solution {
        public List<Integer> findClosestElements(int[] arr, int k, int x) {
            final List<Integer> ans = Arrays.stream(arr).boxed().sorted(Comparator.comparingInt(a -> Math.abs(a - x))).collect(Collectors.toList());
            Collections.sort(ans.subList(0, k));
            return ans.subList(0, k);
        }
    }
    

    BTW, Collections.sort() actually uses extra space. It does the following in the background. You may check its source code here.

    Object[] a = list.toArray();
    Arrays.sort(a);
    

    And there is a typo in the explanation: Collections.sort() uses merge sort

    Binary search

    I think the most difficult point is to understand index = -index - 1. Well, Collections.binarySearch() returns -(insertion point) - 1, which is index. So -index - 1 is just insertion point, which is the index of the element if it is to be added to the array and also keep the array sorted.

    For example, for arr = [2, 3, 5, 6], if x = 1, the insertion point will be at 0 (inserting x at index 0 will still keep arr sorted); similarly, if x = 7, the insertion point will become 4; and if x = 4, the insertion point will become 2.

    BTW, the code can be simplified a little bit.

    class Solution {
        public List<Integer> findClosestElements(int[] a, int k, int x) {
            final List<Integer> arr = Arrays.stream(a).boxed().collect(Collectors.toList());
            final int n = arr.size();
            if (x <= arr.get(0)) {
                return arr.subList(0, k);
            } else if (x >= arr.get(n - 1)) {
                return arr.subList(n - k, n);
            } else {
                int index = Collections.binarySearch(arr, x);
                if (index < 0) {
                    index = -index - 1;
                }
                int low = Math.max(0, index - k);
                int high = Math.min(n - 1, index + k - 1);
                while (high - low + 1 > k) {
                    if (x - arr.get(low) <= arr.get(high) - x) {
                        high--;
                    } else {
                        low++;
                    }
                }
                return arr.subList(low, high + 1);
            }
        }
    }
    

  • 0
    M

    can anyone tell me how to write a two-parameter comp function in c++... I try to use a static variable, changing it to x before using the sort function but it ended up compile error saying undefined reference to Solution::xxx (that's my variable)...


  • 0
    R

    the second solution. In the while loop:while (high - low > k - 1),I don't think you have to check if low <0 or high > arr.size() - 1,since what you do with int low = Math.max(0, index - k - 1), high = Math.min(arr.size() - 1, index + k - 1), has guaranteed that low and high are valid.


  • 0
    S

    Hey, I've faced a test, and understood that I had misunderstood the task.
    Maybe I'm even a single person who did this mistake, but for me preferences sound like:

    1. Select the closest by distance
    2. If distances are the same - select smaller element
      So I was surprised when I got this result, because 9 is much closer to 4 than 0.
      I think it would be great to clarify this in description.

    Input:
    [0,1,1,1,2,3,6,7,8,9]
    9
    4
    Output:
    [1,1,1,2,3,6,7,8,9]
    Expected:
    [0,1,1,1,2,3,6,7,8]


  • 0
    S

    I mean I thought element have to be closest by position in array


  • 0
    D

    class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
    List<Integer> list = new ArrayList<>();
    if(arr.length == 0 | arr == null) {
    return list;
    }
    if (x <= arr[0]) {
    for(int i = 0; i < k; i++) {
    list.add(arr[i]);

            }
            return list;
        }
        if (x >= arr[arr.length - 1]) {
            for(int i = arr.length - k ; i <= arr.length - 1; i++) {
                list.add(arr[i]);
            }
            //Arrays.sort(list);
            return list;
        }
        int index = binarySearch(arr, x);
        int low = Math. max(0, index - k + 1);
        int high = Math.min(arr.length - 1, index + k - 1);
        // if arr[index] - arr[low] <= arr[high] - arr[index], high--
        while(high - low > k - 1){
            if (low < 0 || x - arr[low] <= arr[high] - x){
                high--;
            }
            else if (high > arr.length-1 || x - arr[low] > arr[high] - x){
                low++;
            }
        }
        for(int i = low; i <= high; i++) {
            list.add(arr[i]);
        }
        
        return list;
    }
    
    private int binarySearch(int[] arr, int x) {
        int start = 0, end = arr.length - 1;
        while(start + 1 < end) {
            int mid = start + (end - start) / 2;
            if(arr[mid] == x) {
                return mid;
            }
            if(arr[mid] > x) {
                end = mid;
            }
            else {
                start = mid;
            }
        }
        if(arr[start] == x){return start;}
        if(arr[end] == x){return end;}
        return start;
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.