leetcode 719. Find K-th Smallest Pair Distance 第k小的绝对距离 + 暴力计算真棒

朴灿烈づ我的快乐病毒、 2022-06-03 09:41 125阅读 0赞

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.

本题题意很简单，直接暴力去做即可

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    
    
    class Solution 
    {
    public:
        int smallestDistancePair(vector<int>& nums, int k) 
        {
            int n = nums.size(), N = 1000000;
            vector<int> count(N, 0);
            for (int i = 0; i < n; i++)
            {
                for (int j = i + 1; j < n; j++)
                {
                    count[abs(nums[i] - nums[j])]++;
                }
            }
    
            for (int i = 0; i < count.size(); i++)
            {
                if (count[i] >= k)
                    return i;
                else
                    k -= count[i];
            }
            return -1;
        }
    };