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.


Log in to reply
 

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