719. Find K-th Smallest Pair Distance

Given an integer array, return the k-th smallest distance among all the pairs. The distance of a pair (A, B) is defined as the absolute difference between A and B.

Example 1:

Input:

nums = [1,3,1]

k = 1

Output: 0

Explanation:

Here are all the pairs:

(1,3) -> 2

(1,1) -> 0

(3,1) -> 2

Then the 1st smallest distance pair is (1,1), and its distance is 0.

Note:

2 <= len(nums) <= 10000.
0 <= nums[i] < 1000000.
1 <= k <= len(nums) * (len(nums) - 1) / 2.

Approach #1: Brute Force.[Memory Limit Exceeded]

class Solution {

public:

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

        int len = nums.size();

        vector<int> temp;

        for (int i = 0; i < len; ++i) {

            for (int j = i+1; j < len; ++j) {

                int sub = abs(nums[i] - nums[j]);

                temp.push_back(sub);

            }

        }

        sort(temp.begin(), temp.end());

        return temp[k-1];

    }

};

Approach #2: Brute Force. [Bucter Sort]

class Solution {

public:

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

        int len = nums.size();

        sort(nums.begin(), nums.end());

        int N = nums.back();

        vector<int> container(N+1, 0);

        for (int i = 0; i < len; ++i) {

            for (int j = i+1; j < len; ++j) {

                ++container[nums[j]-nums[i]];

            }

        }

        for (int i = 0; i <= N; ++i) {

            k -= container[i];

            if (k <= 0) return i;

        }

        return 0;

    }

};

Runtime: 580 ms, faster than 13.29% of C++ online submissions for Find K-th Smallest Pair Distance.

Approach #2: Binary Search + DP

class Solution {

public:

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

        int len = nums.size();

        sort(nums.begin(), nums.end());

        int l = 0;

        int r = nums.back() - nums.front();

        while (l <= r) {

            int count = 0;

            int j = 0;

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

            for (int i = 0; i < len; ++i) {

                while (j < len && nums[j] - nums[i] <= m) j++;

                count += j - i - 1;

            }

            count >= k ? r = m - 1 : l = m + 1;

        }

        return l;

    }

};

Runtime: 16 ms, faster than 43.93% of C++ online submissions for Find K-th Smallest Pair Distance.

Analysis:

nums = [1, 1, 3, 5, 8] total pairs = 10

suppose: m = 3

i : nums[i]	j : nums[j]	dp[i]	pairs
0 : 1	3 : 5	2	1:1; 1:3
1 : 1	3 : 5	3	1:3
2 : 3	4 : 8	4	3:5
3 : 5	end	5	5:8

dp[i] = dp[i-1] + (j - i - 1);

we can use a constant to instead dp array.

巴特西

719. Find K-th Smallest Pair Distance

最新文章

热门文章