Java&C++题解与拓展——leetcode719.找出第K小的数对距离【么的新知识】

每日一题做题记录，参考官方和三叶的题解

目录

• 题目要求
• 思路：双指针+二分
• • Java
  • C++
  • Rust
• 总结

题目要求

思路：双指针+二分

• 二分逐个枚举数对距离，检验是否满足条件，检验过程中用双指针枚举遍历查找。
• 二分的值就是目标值，假设当前二分到 m m m：
  • 枚举左端点 l l l，找第一个超出 m m m的右端点 r r r，那当前合法的数对距离个数为 c n t = r − l − 1 cnt=r-l-1 cnt=r−l−1。

Java

class Solution {
    public int smallestDistancePair(int[] nums, int k) {
        int n = nums.length, cnt;
        Arrays.sort(nums);
        int left = 0, right = nums[n - 1] - nums[0];
        while(left < right) {
            int m = left + right >> 1;
            cnt = 0; // 小于m的数对距离个数
            for(int l = 0, r = 1; l < n; l++) {
                while(r < n && nums[r] - nums[l] <= m)
                    r++;
                cnt += r - l - 1;
            }
            if(cnt >= k)
                right = m;
            else
                left = m + 1;
        }
        return right;
    }
}

• 时间复杂度： O ( n ( log ⁡ n + log ⁡ D ) ) O(n(\log n+\log D)) O(n(logn+logD))
• 空间复杂度： O ( log ⁡ n ) O(\log n) O(logn)

C++

class Solution {
public:
    int smallestDistancePair(vector<int>& nums, int k) {
        int n = nums.size(), cnt;
        sort(nums.begin(), nums.end());
        int left = 0, right = nums[n - 1] - nums[0];
        while(left < right) {
            int m = left + right >> 1;
            cnt = 0; // 小于m的数对距离个数
            for(int l = 0, r = 1; l < n; l++) {
                while(r < n && nums[r] - nums[l] <= m)
                    r++;
                cnt += r - l - 1;
            }
            if(cnt >= k)
                right = m;
            else
                left = m + 1;
        }
        return right;
    }
};

• 时间复杂度： O ( n ( log ⁡ n + log ⁡ D ) ) O(n(\log n+\log D)) O(n(logn+logD))
• 空间复杂度： O ( log ⁡ n ) O(\log n) O(logn)

Rust

impl Solution {
    pub fn smallest_distance_pair(mut nums: Vec<i32>, k: i32) -> i32 {
        nums.sort();
        let n = nums.len();
        let (mut left, mut right) = (0, nums[n - 1] - nums[0]);
        let mut cnt;
        while left < right {
            let m = left + right >> 1;
            let mut r = 1;
            cnt = 0;
            for l in 0..n {
                while r < n && nums[r] - nums[l] <= m {
                    r += 1;
                }
                cnt += (r- l - 1) as i32;
            }
            if cnt >= k {
                right = m;
            }
            else {
                left = m + 1;
            }
        }
        right
    }
}

• 时间复杂度： O ( n ( log ⁡ n + log ⁡ D ) ) O(n(\log n+\log D)) O(n(logn+logD))
• 空间复杂度： O ( log ⁡ n ) O(\log n) O(logn)

总结

总是想不到二分的思路，要好好反思一下，有二分思路就是简单模拟题辣。

【喜欢这个题号、所以认真做题 说得好像其他题没有认真做一样~】

欢迎指正与讨论！