【Day 41 】2021-10-20 - 822. Kth-Pair-Distance

[azl397985856]

822. Kth-Pair-Distance

入选理由

暂无

题目地址

https://binarysearch.com/problems/Kth-Pair-Distance

前置知识

• 排序
• 二分法

  题目描述

  
  Given a list of integers nums and an integer k, return the k-th (0-indexed) smallest abs(x - y) for every pair of elements (x, y) in nums. Note that (x, y) and (y, x) are considered the same pair.

Constraints

n ≤ 100,000 where n is the length of nums Example 1 Input nums = [1, 5, 3, 2] k = 3 Output 2 Explanation Here are all the pair distances:

abs(1 - 5) = 4 abs(1 - 3) = 2 abs(1 - 2) = 1 abs(5 - 3) = 2 abs(5 - 2) = 3 abs(3 - 2) = 1 Sorted in ascending order we have [1, 1, 2, 2, 3, 4].

[yanglr]

思路

本题类似于 Leetcode 719. 找出第 k 小的距离对。

区别在于: 本题的k是0-indexed的, 即k从0开始算。 Leetcode 719的k是1-indexed的, 即k从1开始算。

第一感觉是topK问题, 用优先队列即可解决, 但试了一下, 超时了。

// 方法1: 优先队列
int solve(vector<int>& nums, int k) {
    const int len = nums.size();
    priority_queue<int, vector<int>, greater<>> q; // 小顶堆

    for (int i = 0; i < len - 1; i++)
    {
        for (int j = i + 1; j < len; j++)
        {
            q.push(abs(nums[i] - nums[j]));
        }
    }
    if (k > q.size() - 1) return 0;
    while (k > 0)
    {
        q.pop();
        k--;
    }
    int res = q.top();
    return res;
}

方法2: 二分搜索

假如将这个第 k 小的距离 (k-th smallest )记作value, 假设我们知道这个value了，能不能通过什么方法判断这个value是取大了，还是取小了？

也就是在所有不同pair的距离组成的数组中，<= value 的有k个; 那么如果value给小了, <= value 将会少于k个; 如果value给大了, <= value 将会多于k个。

也可以反过来看: 如果 <= value 的少于k个, 说明value取小了, 如果 <= value 的多于k个, 说明value取大了。

先sort, 此时value的最大值为nums[N - 1] - nums[0], 最小值可以从0开始。 后面进行二分搜索~

代码:

实现语言: C++

bool possible(vector<int>& nums, int d, int k)
{
    const int N = nums.size();
    long count = 0; // count可能会超过2^31, 故用long存储比较稳妥
    int i = 0, j = 0;
    while (i < N || j < N)
    {
        while (j < N && nums[j] - nums[i] <= d) j++;
        count += j - i - 1;
        i++;
    }
    return count >= k;
};
int solve(vector<int>& nums, int k) {
    const int N = nums.size();
    sort(begin(nums), end(nums));
    k += 1;      //  0-indexed -> 1-indexed
    int left = 0, right = nums[N - 1] - nums[0];
    while (left < right)
    {
        int guess = left + (right - left) / 2; // guess: mid
        if (possible(nums, guess, k))
            right = guess;
        else
            left = guess + 1;
    }
    return left;
}

复杂度分析

• 时间复杂度：时间复杂度大约是 O(N logN), 其中N为数组长度, 因为一开始用了sort
• 空间复杂度：取决于排序的空间消耗

[yachtcoder]

'Possible' binary search. O(nlgnlgN), where N=(max(nums)-min(nums)); O(1)

class Solution:
    def solve(self, nums, k):
        nums.sort()
        N = len(nums)
        def possible(d):
            #if we can find more than k pairs with abs diff less or equal to d.
            count = 0
            for i in range(N):
                target = nums[i] + d
                idx = bisect_right(nums, target) - 1
                count += min(idx, N-1) - i
                if count > k: return True #k is 0-based.
            return False
        l, r = 0, nums[-1] - nums[0]
        while l <= r:
            mid = (l+r)//2
            if possible(mid):
                r = mid - 1
            else:
                l = mid + 1
        return l

[pophy]

思路

• 2分猜distance D
  • 排序原数组， D的取值范围为【数组内最小差值：数组内最大差值】
  • 假设当前D = mid
  • 遍历数组，下标为i，统计数组内满足 nums[j] - nums[i] <= mid的个数， 记为count
    • j 可以通过2分找Upper bound得到
  • 如果count < k, 说明mid偏小 low = mid +1, 否则 high = mid

Java Code

public class KthPairDistance {

    public int solve(int[] nums, int k) {
        k += 1;
        Arrays.sort(nums);
        int low = Integer.MAX_VALUE, high = nums[nums.length - 1] - nums[0];
        for (int i = 1; i < nums.length; i++) {
            low = Math.min(low, nums[i] - nums[i - 1]);
        }
        while (low < high) {
            int mid = low + (high - low) / 2;
            int count = countPairs(nums, mid);
            if (count < k) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }

    private int countPairs(int[] nums, int mid) {
        int n = nums.length, res = 0;
        for (int i = 0; i < n; i++) {
            res += upperBound(nums, i, n - 1, nums[i] + mid) - i - 1;
        }
        return res;
    }

    private int upperBound(int[] a, int low, int high, int key) {
        if (a[high] <= key) return high + 1;
        while (low + 1 < high) {
            int mid = low + (high - low) / 2;
            if (key >= a[mid]) {
                low = mid;
            } else {
                high = mid;
            }
        }
        if (a[low] > key) {
            return low;
        }
        return high;
    }

时间&空间

• 时间 O( N * log(n)^2 )
• 空间 O(1)

[Yufanzh]

Intuition

Binary search solution space for the distance difference is within [0, max(nums) - min(nums)] binary search is used to determine if the number of pairs with difference no greater than dif is larger or smaller than k To calculate the number of pairs with difference no greater than dif, we will use two pointers to count and record this number Another thing to pay attention is that: then solution space is determined, difference doesn't necessarily to be all values within the solution space So for this problem, the framework we will use is the "left boundary" framework

Algorithm in python3

class Solution:
    def smallestDistancePair(self, nums: List[int], k: int) -> int:
        nums.sort()
        l = 0
        r = nums[-1] - nums[0]
        def cnt_smaller_than(dif):
            # use two pointers to calculate
            ans = 0
            i = 0
            for j in range(1, len(nums)):
                while nums[j] - nums[i] > dif:
                    i += 1
                ans += j - i
            return ans

    # point 1: since our help function is acount, then this 0-index based kth smallest should first change to one-index based to do the following question
    # point 2: dif in arraylist doesn't necessarily includes all the value in [l,r], so it is a left boundary binary search problem 
        k += 1
        while l <= r:
            mid = (r + l) // 2
            if cnt_smaller_than(mid) >= k:
                r = mid - 1
            else:
                l = mid + 1

        return l

Complexity Analysis

• Time complexity: O(nlogn)
• Space complexity: O(N)

[zliu1413]

class Solution(object): def smallestDistancePair(self, nums, k): nums.sort() n = len(nums) left,right = 0,nums[-1]-nums[0] while left<=right: mid = (left+right)//2 if self.checkIsPossible(nums,k,mid): right = mid-1 else: left = mid+1 return left

def checkIsPossible(self,nums,k,d):
    n = len(nums)
    count = 0
    for i in range(n):
        target = nums[i]+d
        idx = bisect.bisect_right(nums,target)-1
        count += min(idx,n-1) - i
        if count>=k: return True
    return False

time: O(nlogn + nlogW), w = max(nums)-min(nums) space: O(1)

[zhangzhengNeu]

class Solution: def smallestDistancePair(self, nums: List[int], k: int) -> int: nums.sort() l = 0 r = nums[-1] - nums[0] def cnt_smaller_than(dif):

use two pointers to calculate

        ans = 0
        i = 0
        for j in range(1, len(nums)):
            while nums[j] - nums[i] > dif:
                i += 1
            ans += j - i
        return ans

# point 1: since our help function is acount, then this 0-index based kth smallest should first change to one-index based to do the following question
# point 2: dif in arraylist doesn't necessarily includes all the value in [l,r], so it is a left boundary binary search problem 
    k += 1
    while l <= r:
        mid = (r + l) // 2
        if cnt_smaller_than(mid) >= k:
            r = mid - 1
        else:
            l = mid + 1

    return l

[zhangzz2015]

思路

• 转换该问题，反问题，如果求当diff = m ，有多少pair diff 小于 < m。当diff 增加时候，满足该条件的pair 对增加，diff减少，满足该条件的pai对减少，这个条件可以用来做binary search。我们找到对应的diff ， pair对的数目正好等于k，主要要考虑有多个diff，得到的k相同，我们求解是的左边界，则是条件要求解的diff值，该二分为计数二分，需要另外一个辅助函数，该函数用来求解给定diff m的情况下，求解小于等于m有多少pair对，[i j]，可固定i，找到最大的 a[j] == m+a[i]。该方法也可使用二分搜索。时间复杂度为O(nlogn)，空间复杂度为O(1)。

• 另外要注意binary search case集合更大，需要用long 来保存count。

  关键点

代码

• 语言支持：C++

C++ Code:

     //  find index  right boundary. 
    //   [right left]   right <=val  left > val 
    int binarySearch(vector<int>& nums, int left, int right, int val)
    {

        while(left<=right)
        {
            int middle = left + (right - left)/2; 

            if(nums[middle]>val)
            {
                right = middle -1;
            }
            else
            {
                left = middle +1;
            }
        }

        return right; 
    }

    //   a[j] -  a[i] <=k 
    long long lessThanKPair(vector<int>& nums, int k)
    {

        long long count =0; 
        for(int i=0; i< nums.size()-1; i++)
        {

            int index = binarySearch(nums, i+1, nums.size()-1, nums[i]+k); 

            count += (index -i ); 
        }

        return count; 
    }

int solve(vector<int>& nums, int k) {

        k++;  // 转换 0 index to 1 index
        sort(nums.begin(), nums.end()); 

        int left =0; 
        int right = nums[nums.size()-1] - nums[0]; 
        // [left right]   [right left]   right<=k left > k 
        while(left<=right)
        {
            int middle = left + (right - left)/2; 

            long pairNum = lessThanKPair(nums, middle); 
           // cout << "middle:" << middle << "pairNum:" << pairNum<<"\n";
            if(pairNum <k)
            {
                left = middle+1; 
            }
            else 
            {
                right = middle-1; 
            }
        }

        return left;    

}

[leo173701]

参考lc 719. Find K-th Smallest Pair Distance 思路总结：

1. 对数组进行排序
2. low = 0, high = nums[-1] - nums[0] (也就是最大值减去最小值， 自然得到最大差值)
3. 进行二分搜索， 这里需要特别注意怎么引入 k的

class Solution {
    public int smallestDistancePair(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length, low = 0, hi = nums[n-1] - nums[0];
        while (low < hi) {
            int cnt = 0, j = 0, mid = (low + hi)/2;
            for (int i = 0; i < n; ++i) {
                while (j < n && nums[j] - nums[i] <= mid) ++j;
                cnt += j - i-1;
            }
            if (cnt >= k) 
                hi = mid;

            else low = mid + 1;
        }

        return low;
    }
}

[JiangyanLiNEU]

class Solution:
    def solve(self, nums, k):
        nums.sort()
        length = len(nums)
        def qualified(d):
            count = 0
            for i in range(N):
                target = nums[i] + d
                idx = bisect_right(nums, target) - 1
                count += min(idx, N-1) - i
                if count > k: return True
            return False
        l, r = 0, nums[-1] - nums[0]
        while l <= r:
            mid = (l+r)//2
            if qualified(mid):
                r = mid - 1
            else:
                l = mid + 1
        return l

[wangzehan123]

class Solution:
    def solve(self, nums, k):
        nums.sort()
        N = len(nums)
        def possible(d):
            #if we can find more than k pairs with abs diff less or equal to d.
            count = 0
            for i in range(N):
                target = nums[i] + d
                idx = bisect_right(nums, target) - 1
                count += min(idx, N-1) - i
                if count > k: return True #k is 0-based.
            return False
        l, r = 0, nums[-1] - nums[0]
        while l <= r:
            mid = (l+r)//2
            if possible(mid):
                r = mid - 1
            else:
                l = mid + 1
        return l

[zol013]

和昨天的题一样，二分查找解空间为[0, max(nums) - min(nums)], max(nums) - min(nums)为最大的distance。 写一个helper函数 count_not_greater (滑动窗口)来数 distance 比mid小的pair的个数。然后对count_not_greater 使用二分查找 Python 3 code

class Solution:
    def smallestDistancePair(self, nums: List[int], k: int) -> int:
        nums.sort()

        def count_not_greater(diff):
            i = 0
            ans = 0 
            for j in range(1, len(nums)):
                while nums[j] - nums[i] > diff:
                    i += 1
                ans += j - i
            return ans

        l, r = 0, nums[-1] - nums[0]
        while l <= r:
            mid = (l + r)//2
            if count_not_greater(mid) >= k:
                r = mid - 1
            else:
                l = mid + 1
        return l

Time Complexity: O(nlogn) Space Comlpexity: O(1)

[yukicoding]

class Solution(object):
def smallestDistancePair(self, nums, k):
nums.sort()
n = len(nums)
left,right = 0,nums[-1]-nums[0]
while left<=right:
mid = (left+right)//2
if self.checkIsPossible(nums,k,mid):
right = mid-1
else:
left = mid+1
return left

def checkIsPossible(self,nums,k,d):
    n = len(nums)
    count = 0
    for i in range(n):
        target = nums[i]+d
        idx = bisect.bisect_right(nums,target)-1
        count += min(idx,n-1) - i
        if count>=k: return True
    return False
time: O(nlogn + nlogW), w = max(nums)-min(nums)
space: O(1)

[ghost]

题目

Kth Pair Distance https://binarysearch.com/problems/Kth-Pair-Distance

思路

Binary Search

代码

class Solution:
    def solve(self, nums, k):
        nums.sort()
        l, r = 0, nums[-1]-nums[0]
        k+=1

        def helper(target):
            i = res = 0

            for j in range(1, len(nums)):
                while nums[j] - nums[i] > target:
                    i+=1
                res += j-i

            return res

        while(l <= r):
            mid = (l+r) // 2
            if helper(mid) >= k:
                r = mid - 1
            else:
                l = mid + 1

        return l

复杂度

Space: O(n) Time: O(nlogn)

[yingliucreates]

link:

Kth Pair Distance https://binarysearch.com/problems/Kth-Pair-Distance

连抄的答案也没看懂 >_< 太菜啦

代码 Javascript

const kthPairDistance = function (nums, k) {
  nums.sort((a, b) => a - b);
  let maxDistance = nums[nums.length - 1] - nums[0];
  let distanceCounts = new Array(maxDistance + 1).fill(0);
  for (let i = 1; i < nums.length; i++) {
    for (let j = 0; j < i; j++) {
      distanceCounts[nums[i] - nums[j]]++;
    }
  }
  let t = 0;
  for (let i = 0; i < distanceCounts.length; i++) {
    t += distanceCounts[i];
    if (t >= k) return i;
  }
};

console.log(kthPairDistance([1, 5, 3, 2], 1));

[banjingking]

思路

抄的答案qaq，二分法

代码

bool ok(int diff, int k, vector<int>& nums) {
    long count = 0;
    int n = nums.size(), r = 0;
    for (int l = 0; l < n; l++) {
        while (r < n && nums[r] - nums[l] <= diff) {
            r++;
        }
        count += (r - l - 1);
    }
    return count >= k;
}

int solve(vector<int>& nums, int k) {
    sort(nums.begin(), nums.end());
    k++;
    int l = 0, r = nums[nums.size() - 1] - nums[0], res = INT_MAX;
    while (l <= r) {
        int m = l + (r - l) / 2;
        if (ok(m, k, nums)) {
            res = min(res, m);
            r = m - 1;
        } else {
            l = m + 1;
        }
    }
    return res;
}

Time complexity

空间复杂度: O(1)

时间复杂度: O(nlog(maxdiff))

[bolunzhang2021]

参考官方题解

class Solution:
    def solve(self, A, k):
        A.sort()
        h = [(A[i] - A[i-1], i-1,i) for i in range(1, len(A))]
        heapq.heapify(h)

        while True:
            top, i, j = heapq.heappop(h)
            if not k: return top
            k -= 1
            if j + 1 < len(A): heapq.heappush(h, (A[j+1] - A[i], i, j + 1))

时间复杂度: O(nlogn) 空间复杂度: O(1)

[Daniel-Zheng]

思路

二分查找 + 滑动窗口。

代码(C++)

class Solution {
public:
    int smallestDistancePair(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int l = 0, r = nums.back() - nums[0];
        while (l < r) {
            int mid = l + (r - l) / 2;
            int count = 0, left = 0;
            for (int right = 0; right < nums.size(); right++) {
                while (nums[right] - nums[left] > mid) left++;
                count += right - left;
            }
            if (count >= k) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
};

复杂度分析

• 时间复杂度：O(NLogN)
• 空间复杂度：O(1)

[hengistchan]

class Solution:
    def solve(self, nums, k):
        nums.sort()
        length = len(nums)
        def qualified(d):
            count = 0
            for i in range(N):
                target = nums[i] + d
                idx = bisect_right(nums, target) - 1
                count += min(idx, N-1) - i
                if count > k: return True
            return False
        l, r = 0, nums[-1] - nums[0]
        while l <= r:
            mid = (l+r)//2
            if qualified(mid):
                r = mid - 1
            else:
                l = mid + 1
        return l

[ai2095]

Kth Pair Distance

https://binarysearch.com/problems/Kth-Pair-Distance https://leetcode.com/problems/find-k-th-smallest-pair-distance/

Topics

• sort

Similar Questions

Hard

Medium

思路

binary search + sliding window

代码 Python

class Solution:
    def solve(self, nums, k):
        def possible(guess):
            #Is there k or more pairs with distance <= guess?
            count = left = 0
            for right, x in enumerate(nums):
                while x - nums[left] > guess:
                    left += 1
                count += right - left
            return count >= k

        nums.sort()
        lo = 0
        hi = nums[-1] - nums[0]
        while lo < hi:
            mi = (lo + hi) // 2
            if possible(mi):
                hi = mi
            else:
                lo = mi + 1

        return lo

复杂度分析

时间复杂度： O(NlogW+NlogN), where N is the length of nums, and W is equal to nums[nums.length - 1] - nums[0]
空间复杂度：O(1)

[tongxw]

思路

这题关键是能看出来是用二分。。。

代码

import java.util.*;

class Solution {
    public int solve(int[] nums, int k) {
        Arrays.sort(nums); // O(NlogN)
        int absMin = 0;
        int absMax = nums[nums.length-1] - nums[0];

        while (absMin <= absMax) { // O(log(maxNum - minNum))
            int absMid = (absMin + absMax) / 2;
            System.out.println("mid: " + absMid);
            if (count(nums, absMid) <= k) { // O(N)
                absMin = absMid + 1;
            } else {
                absMax = absMid - 1;
            }
        }

        return absMin;
    }

    private long count(int[] nums, int targetDiff) {
        // how many pairs abs(diff) <= target?
        long counter = 0;

        // sliding window
        int l = 0;
        for (int r=1; r<nums.length; r++) {
            while (nums[r] - nums[l] > targetDiff) {
                l++;
            }

            counter += r - l;
        }

        // System.out.println("diff: " + targetDiff + " counter: " + counter);
        return counter;
    }
}

• TC: O(nlogn) + O(nlog(maxNum - minNum))
• SC: O(1)

[shawncvv]

思路

二分法

代码

Python3 Code

class Solution:
    def solve(self, A, k):
        A.sort()
        def count_not_greater(diff):
            i = ans = 0
            for j in range(1, len(A)):
                while A[j] - A[i] > diff:
                    i += 1
                ans += j - i
            return ans
        l, r = 0, A[-1] - A[0]
        k += 1 # zero based -> one based
        while l <= r:
            mid = (l + r) // 2
            if count_not_greater(mid) >= k:
                r = mid - 1
            else:
                l = mid + 1
        return l

复杂度

• 时间复杂度：O(nlogn)
• 空间复杂度：O(n)

[yan0327]

好像有点掌握二分的技巧了。关键是通过二分找到一个值，然后通过这个值去判断它是否满足第K小的情况 其次就是滑动窗口找符合值，每次count += j-i 意味着把i到j之间的组合都加了一遍，这些都是符合条件的。【大前提是排序！】

func smallestDistancePair(nums []int, k int) int {
    n := len(nums)
    sort.Ints(nums)
    left,right := 0,nums[n-1]-nums[0]
    for left < right{
        guess := left + (right-left)/2
        if possible(nums,guess,k){
            right = guess
        }else{
            left = guess+1
        }
    }
    return left
}
func possible(nums []int, d int, k int) bool{
    count := 0
    i := 0
    for j,x := range nums{
        for x - nums[i]>d{
            i++
        }
        count += j-i
    }
    return count >= k
}

时间复杂度：O（NogN） 空间复杂度：O(1)

[ZacheryCao]

Idea:

Binary search. Search range [0, max(nums) - min(nums)]. For each possible guess, we need to decide whether it has >= k pairs of elements whose difference if smaller than or equal to guess/ If so, we need to decrease the right side, otherwise we need to increase the left side.

Code:

class Solution:
    def solve(self, nums, k):
        nums.sort()
        ans = 0
        l, r = 0, nums[-1] - nums[0]
        while l <= r:
            mid = l + (r - l)//2
            if self.possible(nums, k + 1, mid):
                ans = mid
                r = mid - 1
            else:
                l = mid + 1
        return ans

    def possible(self, nums, k, mid):
        ans = 0
        left, right = 0, 0
        while left < len(nums) or right < len(nums):
            while right < len(nums) and nums[right] - nums[left] <= mid:
                right += 1
            ans += right - left - 1
            left += 1
        return ans >= k

Complexity:

Time: O(N * log max(max(nums) - min(nums), N)). Sort is O(N log N). We need to scan through all possible elements in the array to get all pairs' difference, which is O(N). For the binary search is O(log (max(nums) - min(nums)). So, the total complexity, excluding the sort, is O( N log (max(nums) - min(nums)) Space: O(1)

[BpointA]

思路

参考官方题解，二分法+滑动窗口

Python3代码

class Solution:
    def solve(self, nums, k):
        nums.sort()
        left=0
        right=nums[-1]-nums[0]
        def can(diff):
            i=0
            cnt=0
            for j in range(1,len(nums)):
                while i<j and nums[j]-nums[i]>diff:
                    i+=1
                cnt+=i
            m=len(nums)
            return m*(m-1)/2-cnt

        k+=1
        while left<=right:
            mid=(left+right)//2

            if can(mid)>=k:
                right=mid-1
            else:
                left=mid+1
        return left

复杂度

时间复杂度：O(nlogn) 空间复杂度：O(n)

[BlueRui]

Problem Kth Pair Distance

Algorithm

• Let diff be the k-th (0-indexed) smallest abs(x - y) for every pair of elements (x, y) in nums. The problem is to find the smallest value of diff such that there are k pairs whose absolute difference is no greater than diff.
• We start by finding a feasible range of diff, then use binary search to shrink the range to find the smallest one.
• To shrink the range, we check if there are more than k pairs whose absolute diff is greater than current diff then discard half of the search space of diff.
• We will sort the array first, then the initial range for diff is [0, nums[nums.length - 1] - nums[0]].

Complexity

• Time Complexity: O(NlogN). Sorting is O(NlogN). Counting pairs with diff no greater than a value is O(N), and we do it O(logN) times.
• Space Complexity: O(N). Space for sorting.

Code

Language: Java

public int solve(int[] nums, int k) {
    Arrays.sort(nums);
    int left = 0;
    int right = nums[nums.length - 1] - nums[0];
    while (left <= right) {
        int mid = left + (right - left) / 2;
        // k + 1 as k is 0-indexed
        if (countNoGreaterThanDiff(nums, mid) >= k + 1) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

private long countNoGreaterThanDiff(int[] nums, int diff) {
    long count = 0;
    int i = 0;
    for (int j = 1; j < nums.length; j++) {
        while (nums[j] - nums[i] > diff) {
            i++;
        }
        count += j - i;
    }
    return count;
}

[okbug]

class Solution {
public:
    int smallestDistancePair(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int l = 0, r = nums.back() - nums[0];
        while (l < r) {
            int mid = l + (r - l) / 2;
            int count = 0, left = 0;
            for (int right = 0; right < nums.size(); right++) {
                while (nums[right] - nums[left] > mid) left++;
                count += right - left;
            }
            if (count >= k) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
};

[james20141606]

Day 41: 817. Kth Pair Distance (binary search, sliding window)

• Problem Link

  • 817. Kth Pair Distance

• Ideas

  • This is a hard binary search problem, similar to yesterday's problem. Since we could know the min and max of the distance, which is 0 and max(nums) - min(nums). So we just need to search within this range to find the k-th smallest distance.
  • The function to embed in the binary search template is a counter function which could count for a given distance, the pair nums not greater than the distance. To count the satisfied pair's nums, we could use two pointers to shrink the search range. If we calculate pair_num = j - i, we should change k to k + 1, which is not convenient

• Complexity: hash table and bucket

  • Time O(NlogN), sort is O(NlogN), func is O(N), bineary search O(logN) * O(N)
  • Space：O(N)

• Code

class Solution:
    def solve(self, nums, k):
        nums = sorted(nums)  #should sort the array first
        def count_no_greater_pairnums(value):
            i, pair_num = 0, 0
            for j in range(1, len(nums)):
                while abs(nums[j] - nums[i]) > value:
                    i += 1   #shrink i, not j
                pair_num += j - i + 1
            return pair_num

        left, right = 0, nums[-1] - nums[0]
        while left <= right:
            middle = left + (right - left)//2
            if count_no_greater_pairnums(middle) >= k:
                right = middle -1
            else:
                left = middle + 1
        return left

• other resources:

[falconruo]

思路 二分法+滑动窗口 (左闭右闭)

1. 首先要排序，最大的distance就是nums[n - 1] - nums[0], 最小的distance 0
2. 使用二分法每次取中间的距离 m = l + (r - l)/2, 计算nums中距离小于m的pair个数cnt
   • 如果cnt > k, 则表示distance偏大，取左半侧 r = m - 1
   • 否则表示distance偏小(左半侧的距离都小于kth距离),取右半侧 l = m + 1
3. 返回l

复杂度

• 时间复杂度: O(NlogN), N为数组长度
• 空间复杂度: O(1)

代码(C++)

class Solution {
public:
    int smallestDistancePair(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());

        int n = nums.size();
        int l = 0, r = nums[n - 1] - nums[0];

        while (l <= r) {
            int m = l + (r - l)/2;

            if (distIdx(nums, m) > k)
                r = m - 1;
            else
                l = m + 1;
        }

        return l;
    }
private:
    int distIdx(vector<int>& nums, int d) {
        int i = 0, cnt = 0;

        for (int j = 1; j < nums.size(); ++j) {
            while (nums[j] - nums[i] > d) ++i;
            cnt += (j - i); // found all distances <= d
        }

        return cnt;
    }
};

[xieyj17]

class Solution:
    def count_pairs(self, d, nums):
        res = 0
        i = 0
        for j in range(1, len(nums)):
            while nums[j] - nums[i] > d:
                i += 1
            res += (j-i)
        return res

    def solve(self, nums, k):
        nums.sort()
        left = 0
        right = nums[-1] - nums[0]
        while left <= right:
            mid = left + (right-left) // 2
            if self.count_pairs(mid, nums) <= k:
                left = mid + 1
            else:
                right = mid - 1
        return left

有点类似Leetcode 374

Space O(1)

Time: O(NlogN)

[wangyifan2018]

class Solution:
    def solve(self, A, k):
        A.sort()
        def count_not_greater(diff):
            i = ans = 0
            for j in range(1, len(A)):
                while A[j] - A[i] > diff:
                    i += 1
                ans += j - i
            return ans
        l, r = 0, A[-1] - A[0]
        k += 1 # zero based -> one based
        while l <= r:
            mid = (l + r) // 2
            if count_not_greater(mid) >= k:
                r = mid - 1
            else:
                l = mid + 1
        return l

[hewenyi666]

题目名称

822. 翻转卡片游戏

题目链接

https://leetcode-cn.com/problems/card-flipping-game/

题目思路

如果一张牌i 正面与背面相等，那么fronts[i]一定会出现在正面，等于fronts[i]的数一定不想要

用set记录正反面相等的数,把其余的筛出来数逐一过滤是否在set中，然后返回最小的一个

code for Python3

class Solution:
    def flipgame(self, fronts: List[int], backs: List[int]) -> int:
        unused, nums = set(), set()
        for i in range(len(fronts)):
            if fronts[i] == backs[i]:
                unused.add(fronts[i])
            else:
                nums.add(fronts[i])
                nums.add(backs[i])

        res = [n for n in nums if n not in unused]
        return min(res) if res else 0

复杂度分析

• 时间复杂度: O(N)
• 空间复杂度: O(N)

[laofuWF]

class Solution:
    def solve(self, nums, k):
        nums.sort()
        def count_smaller_than(diff):
            res = 0
            i = 0
            for j in range(1, len(nums)):
                while nums[j] - nums[i] > diff:
                    i += 1
                res += j - i
            return res

        left = 0
        right = nums[-1] - nums[0]

        # find right most
        while left <= right:
            mid = left + (right - left) // 2
            count = count_smaller_than(mid)             
            if count > k:
                right = mid - 1
            else:
                left = mid + 1

        return left

[ychen8777]

思路

将数组排序，然后将数组想象成 absolute distance 使用二分查找，left = 0, right = max(nums) - min(nums) \ 不大于mid的数量和k比较，作为向左找向右找的条件

代码

class Solution {
    public int smallestDistancePair(int[] nums, int k) {

        Arrays.sort(nums);
        int l = 0, r = nums[nums.length - 1] - nums[0], mid = -1;

        while (l <= r) {
            mid = l + (r - l) / 2;
            if(count_not_greater(nums, mid) >= k){
                r = mid - 1;
            } else {
                l = mid + 1;
            }          
        }

        return l;

    }

    private int count_not_greater(int[] nums, int diff) {
        int res = 0, i = 0;
        for(int j = 1; j < nums.length; j++) {
            while(nums[j] - nums[i] > diff) {
                i++;
            }
            res += j - i;
        }

        return res;
    }
}

复杂度

时间: O(nlogn) 排序 \ 空间: 取决于排序

[user1689]

题目

https://binarysearch.com/problems/Kth-Pair-Distance

思路

sort + slidingWindow + binarysLeftBoundary

python3

class Solution:
    def solve(self, nums, k):

        # time nlogn + logn
        # space 1

        # find the kth smallest diff pairs
        # diff: [0, max(nums) - min(nums)]
        # binary left boundary
        def countPairs(diff):
            i = 0
            ans = 0
            for j in range(1, len(nums)):
                while (nums[j] - nums[i] > diff):
                    i += 1
                # count pairs eg:1 2 we count it as one pair, so we do not need to add 1
                ans += j - i
            return ans

        nums.sort()
        k += 1
        left, right = 0, nums[-1] - nums[0]
        while (left < right):
            mid = (left + right) >> 1
            if countPairs(mid) >= k:
                right = mid
            else:
                left = mid + 1
        return left

复杂度分析

• time nlon
• space 1

相关题目

1. https://leetcode-cn.com/problems/arranging-coins/
2. https://leetcode-cn.com/problems/koko-eating-bananas/
3. https://binarysearch.com/problems/Minimum-Light-Radius

[hwpanda]

抄答案

const kthPairDistance = function (nums, k) {
  nums.sort((a, b) => a - b);
  let maxDistance = nums[nums.length - 1] - nums[0];
  let distanceCounts = new Array(maxDistance + 1).fill(0);
  for (let i = 1; i < nums.length; i++) {
    for (let j = 0; j < i; j++) {
      distanceCounts[nums[i] - nums[j]]++;
    }
  }
  let t = 0;
  for (let i = 0; i < distanceCounts.length; i++) {
    t += distanceCounts[i];
    if (t >= k) return i;
  }
};

[heyqz]

class Solution:
    def smallestDistancePair(self, nums: List[int], k: int) -> int:
        nums.sort()

        # count the number of pairs that their distance <= diff
        def helper(diff):
            i, cnt = 0, 0
            for j in range(1, len(nums)):
                while nums[j] - nums[i] > diff: 
                    i += 1
                cnt += j - i
            return cnt

        l = 0 
        r = nums[-1] - nums[0] 
        k = k+1

        # binary search m, compute # of pairs whose distance <= m
        while l <= r:
            m = (l + r) // 2 
            if helper(m) >= k:
                r = m - 1 
            else:
                l = m + 1 
        return l

[kidexp]

thoughts

先排序，然后创建一个function，用双指针来找到<=某个差值的数组的pair有多少个

剩下就是找到最小的差值满足有k个pair的差<=这个差值

code

class Solution:
    def solve(self, nums, k):
        nums.sort()

        def count_diff_pair_order(diff):
            start = pair_order = 0
            for i in range(1, len(nums)):
                while nums[i] - nums[start] > diff:
                    start += 1
                pair_order += i - start
            print("pair", diff, pair_order)
            return pair_order

        start, end = 0, nums[-1] - nums[0]
        while start <= end:
            print(start, end)
            mid = (start + end) // 2
            if count_diff_pair_order(mid) >= k + 1:
                end = mid - 1
            else:
                start = mid + 1
        return start

complexity

Time O(nlgn+lg(max_diff)) n是数组的长度，max_diff就是数组中差值的最大值

Space O(1)

[RocJeMaintiendrai]

题目

Given a list of integers nums and an integer k, return the k-th (0-indexed) smallest abs(x - y) for every pair of elements (x, y) in nums. Note that (x, y) and (y, x) are considered the same pair.

思路

对数组进行排序，最小距离为0， 最大距离为nums[n] - nums[0],使用binary search来确定距离，然后双指针来遍历数组来查看当前的比mid小的数组的量是否大于k + 1，大的话说明mid偏大，反之则偏小。 使用滑动窗口思想来计算有多少数组对比mid小。

代码

class Solution {
    public int solve(int[] nums, int k) {
        Arrays.sort(nums);
        int n = 
        int left = 0, right = nums[n - 1] - nums[0];
        while(left <= right) {
            int mid = left + (right - left) / 2;
            if(getCount(nums, mid) >= k + 1) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    private boolean getCount(int[] nums, int dis) {
        int left = 0, count = 0;
        for(int right = 0; right < nums.length; right++) {
            while(nums[right] - nums[left] > dis) {
                left++;
            }
            count += right - left;
        }
        return count;
    }
}

复杂度分析

时间复杂度

O(nlogn)

空间复杂度

O(n)

[Laurence-try]

思路

官方题解

代码

使用语言：Python3

class Solution:
    def solve(self, nums, k):
        nums.sort()
        def count_not_greater(diff):
            i = ans = 0
            for j in range(1, len(nums)):
                while nums[j] - nums[i] > diff:
                    i += 1
                ans += j - i
            return ans
        left, right = 0, nums[-1] - nums[0] # smallest diff = 0, largest diff = max - min (since sorted)
        k += 1
        while left <= right:
            mid = (left + right) >> 1
            if count_not_greater(mid) >= k:
                right = mid - 1
            else:
                left = mid + 1
        return left

复杂度分析 时间复杂度：O(nlogn) 空间复杂度：O(n)

[benngfour]

思路

1. sort array
2. Binary Search

語言

JavaScript

Code Solution

class Solution {
    solve(nums, k) {
        nums = nums.sort((a,b) => a - b);
        let l = 0;
        let r = nums[nums.length - 1] - nums[0];
        let mid;
        while (l <= r) {
            mid = Math.floor((l + r) / 2);
            let res = 0;
            let i = 0;
            for (let j = 1; j < nums.length; j++) {
                while (nums[j] - nums[i] > mid) {
                    i += 1;
                }
                res += j - i;
            }
            if (res > k) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
}

複雜度分析

• 時間複雜度 O(logN)
• 空間複雜度 O(1)

[shixinlovey1314]

Title:719. Find K-th Smallest Pair Distance

Question Reference LeetCode

Solution

First sort the original array, after which we would get the min_num and max_num, thus we know the max_abs, so the answer would be a number between (0, max_abs). We keep on probing the possible answer, each time we have a candidate, go through the array and see how many pairs are smaller than the candidate, if k pairs smaller than candidate, we have found the answer, if >k pairs, we need to decreas the candidate, otherwise increase the candidate.

There's a technic that we can use for each iteration: Since the array is sorted, let's say we have i, j, where i < j. if array[j] - array[i] > max_abs, we know that for any k, k > j, array[k] - array[i] would also > max_abs. so in that case, we advance i, until array[j] - array[i] < max_abs, now for any number m , which i < m < j, we know that array[j] - array[m] would also < max_abs. so now we have found (j - i) pairs that satisfies the constraint.

Code

int getLessCount(vector<int>& nums, int target) {
    int cnt = 0;
    for (int s = 0,e = 1; s < nums.size() && e < nums.size(); e++) {
        while ((nums[e] - nums[s]) > target)
            s++;
        cnt += e - s;
    }

    return cnt;
}

int solve(vector<int>& nums, int k) {
    std::sort(nums.begin(), nums.end());
    int l = 0, r = nums[nums.size() - 1] - nums[0];

    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (getLessCount(nums, mid) >= k)
            r = mid - 1;
        else
            l = mid + 1;
    }

    return l;
}

Complexity

Time Complexity and Explanation

max (o(nlogn), o(nlogm)): Sorting the array takes O(nlogn), to find the candiate, it takes o(logm) where m is the max_abs, during each iteration, it takes o(n) to check if the candidate is the answer. so in total it takes o(nlogm) + o(nlogn) = max (o(nlogn), o(nlogm))

Space Complexity and Explanation

O(1)

[biancaone]

class Solution:
    def solve(self, nums, k):            
        nums.sort()
        k += 1
        left, right = 0, nums[-1] - nums[0]
        while (left < right):
            mid = (left + right) >> 1
            if countPairs(mid) >= k:
                right = mid
            else:
                left = mid + 1
        return left

    def countPairs(diff):
        i = 0
        ans = 0
        for j in range(1, len(nums)):
            while (nums[j] - nums[i] > diff):
                i += 1   
            ans += j - i
        return ans

[guochiscoding]

代码

class Solution {
        solve(nums, k) {
                nums = nums.sort((a, b) => a - b);
                let left = 0, right = nums[nums.length - 1] - nums[0], mid;
                while (left <= right) {
                        mid = Math.floor((left + right) / 2);
                        let res = 0, i = 0;
                        for (let j = 1; j < nums.length; j++) {
                                while ((nums[j] - nums[i]) > mid) {
                                        i += 1;
                                }
                                res += j - i;
                        }
                        if (res > k) {
                                right = mid - 1;
                        } else {
                                left = mid + 1
                        }
                }
                return l;
        }
}

题解

看了官网题解

• sort排序
• 二分法

[zjsuper]

class Solution: def solve(self, nums, k): nums.sort()

count how many pairs < differ

    def count_not_greater(differ):
        start = i = 0
        for j in range(1,len(nums)):
            while nums[j]-nums[start] > differ:
                start += 1
            i += j-start
        return i

    # two pointers
    l = 0
    r = nums[-1]-nums[0]
    #k += 1
    while l <= r:
        mid = (l+r)//2
        if count_not_greater(mid) >k:
            r = mid-1
        else:
            l  = mid+1
    return l

[siyuelee]

Leetcode 719 太难了。。。双指针+二分

class Solution:
    def smallestDistancePair(self, A, k):
        A.sort()
        def count_not_greater(diff):
            i = ans = 0
            for j in range(1, len(A)):
                while A[j] - A[i] > diff:
                    i += 1
                ans += j - i
            return ans
        l, r = 0, A[-1] - A[0]
        while l <= r:
            mid = (l + r) // 2
            if count_not_greater(mid) >= k:
                r = mid - 1
            else:
                l = mid + 1
        return l    

T: nlogn S: 1

[shamworld]

class Solution {
    solve(nums, k) {
        nums.sort((a,b)=>a-b);
        let l = 0, r = nums[nums.length-1] - nums[0];
        while(l <= r){
            const mid = l + Math.floor((r-l)/2);
            if(isFind(nums,mid)>k){
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }

        function isFind(arr,mid){
            let res = 0,i = 0;
            for(let j = 0; j < arr.length; j++){
                while(arr[j]-arr[i]>mid){
                    i++;
                }
                res+=j-i;
            }

            return res;
        }

        return l;
    }
}

[Leonalhq]

思路1

直接遍历并且维护一个最小堆/最大堆，干脆不维护直接所有解排序呗

那就是 n*(n-1) + nlogn n^2, 超时似乎

   lens = len(nums)

​        distances = [0] * lens*(lens-1)

​        index = 0

​        for n, i in enumerate(nums):

​            for m, j in enumerate(nums[i:]):

​                distances[index] = abs(n - m)

​                index = index + 1

​        return sorted(distances[k])

思路2

借鉴了大佬的思路才知道是二分法找到第K个数，不过这个第K个是指距离,讲原数组变成[0,max distance]的常规做法

nums.sort()

l, r =0, nums[-1] - A[0] #max

lens = len(nums)

def count_not_greater(diff):

​   i = ans = 0

​   for m, j in enumerate(nums):

​       while abs(nums[i] - nuns[j]) > diff:

​           i +=1

​       ans = ans + j - i 

​       # plus total counts

   return ans

While l<=r:

​   mid = (l+r)//2

​   if count_not_greater(mid) > k

​       r = mid -1

​   else:

​       r = mid + 1

return l

[GZ712D]

思路

1. sort array
2. Binary Search

代码

class Solution {
        solve(nums, k) {
                nums = nums.sort((a, b) => a - b);
                let left = 0, right = nums[nums.length - 1] - nums[0], mid;
                while (left <= right) {
                        mid = Math.floor((left + right) / 2);
                        let res = 0, i = 0;
                        for (let j = 1; j < 

### 複雜度分析

- 时间 O(logN)
- 空间 O(1)

[chenming-cao]

解题思路

计数二分。先将数组排序，解区间为[0, max - min]。每次通过helper function判断小于当前mid值的数组对数量，不断缩小二分区间，最后得到结果。注意用于求解数组对的helper function可能会溢出，返回类型设为long。

代码

class Solution {
    public int solve(int[] nums, int k) {
        Arrays.sort(nums);
        int l = 0, r = nums[nums.length - 1] - nums[0];
        k++;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (countNotGreater(nums, mid) >= (long) k) {
                r = mid - 1;
            }
            else {
                l = mid + 1;
            }
        }
        return l;
    }
    // return long to avoid overflow
    private long countNotGreater(int[] nums, int diff) {
        long count = 0;
        int i = 0;
        for (int j = 1; j < nums.length; j++) {
            while (nums[j] - nums[i] > diff) {
                i++;
            }
            count += (j - i);
        }
        return count;
    }  
}

复杂度分析

• 时间复杂度：O(nlogn)
• 空间复杂度：O(1)

[thinkfurther]

思路

可能的范围就是0到最大差，所以就要寻找到值，使用二分。难点是二分是否对于某个值可行

代码

class Solution:
    def solve(self, nums, k):
        nums.sort()
        l,r = 0, nums[-1] - nums[0]

        while l<=r:
            mid = (l+r)//2
            if self.count_not_greater(nums, mid) >= k+1:
                r = mid - 1
            else:
                l = mid + 1
        return l

    def count_not_greater(self, nums, diff):
        i = ans = 0
        for j in range(1,len(nums)):
            while nums[j] - nums[i] > diff:
                i += 1
            ans += j -i
        return ans

复杂度

时间复杂度 ：O(Nlog N)

空间复杂度：O(N)