Click here to see the full article post
Now, for every point i, the number of points j with i < j and nums[j] - nums[i] <= guess is prefix[x+guess] - prefix[x] + (count[i] - multiplicity[i]), where count[i] is the number of ocurrences of nums[i] in nums.
I don't get the intuition behind this. Can someone explain please? Thanks
There is a small change in the Approach #1: Heap [Time Limit Exceeded]
from heapq import heapify, heappush, heappop
"""docstring for Solution."""
def KthsmallestpairDist(self, nums, k): #sort the points nums.sort() #[1,1,3] , heap = [(0,0,1),(2,1,2)] heap = [(nums[i+1]-nums[i], i, i+1) for i in xrange(len(nums)-1)] heapify(heap) #Makes it into a BST print(heap) for _ in xrange(k): d, root, nei = heappop(heap) if nei+1<len(nums): heappush(heap, (nums[nei + 1] - nums[root], root, nei + 1)) return d
@richard.zhang.969 I'll give my understanding.
First there is no array
multiplicity is a count of the number of 0 distance pairs at each index. You could just sum this array to get the total number of 0 distance pairs. Then because
guess >= 0, this total always counts towards the number of distance pairs
Now we use
prefix to calculate the remaining distance pairs - those that are
>0 and <= guess. To do that is just
sum(prefix[x + guess] - prefix[x] for x in nums).
prefix[x + guess] - prefix[x] is the count of values in the nums array <= x + guess - the count of values in the nums array <= x. Another way of saying that is: the count of distance pairs that have x as the smaller number in the pair and a distance
>0 and <= guess.
Thank you for the post, really clear and logical. I just have a small question that for the
mi , how do you guarantee there will be a distance equals to the
int mi = (lo + hi) / 2; it's not the actual distance,
@icesnakejin This is because the binary search always finds the smallest mi that satisfies count>=k. Imagine when we find a large mi with count >= k, hi is set to mi, and we keep looking to the left.
For the 3rd solution "Approach #3: Binary Search + Sliding Window [Accepted]", "The logW factor comes from our binary search, and we do O(N) work inside our call to possible (or to calculate count in Java)." I think the complexity for the work inside the call is O(N^2) instead of O(N), since there are two loops. You can optimize it to O(N log N), so the best time complexity for this solution is ( N log N log W + N log N).
@keenencates I'm using python 2. In python 3, use
mi = (lo + hi) // 2 to do integer division instead of float division.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.