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);
            }
        }
    }
    

Log in to reply
 

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