0719 updated.

liuyubobobo · liuyubobobo · commit cd6632da1642 · 2022-06-14T16:08:39.000-07:00
diff --git a/0501-1000/0719-Find-K-th-Smallest-Pair-Distance/cpp-0719/main.cpp b/0501-1000/0719-Find-K-th-Smallest-Pair-Distance/cpp-0719/main.cpp
@@ -1,56 +1,58 @@
 /// Source : https://leetcode.com/problems/find-k-th-smallest-pair-distance/description/
 /// Author : liuyubobobo
-/// Time   : 2017-10-28
+/// Time   : 2022-06-14
 
 #include <iostream>
 #include <vector>
 #include <algorithm>
-#include <set>
 
 using namespace std;
 
-/// Time Complexity: O(nlogn + n^2 + W)
-/// Space Complexity: O(W), where W = max(nums) - min(nums)
+
+/// Binary Search
+/// Time Complexity: O(log(max_dis) * nlogn)
+/// Space Complexity: O(1)
 class Solution {
 public:
     int smallestDistancePair(vector<int>& nums, int k) {
 
-        int dis[1000000];
-        for(int i = 0 ; i < 1000000 ; i ++)
-            dis[i] = 0;
+        int n = nums.size();
 
         sort(nums.begin(), nums.end());
-        for(int i = 0 ; i < nums.size() ; i ++)
-            for(int j = i + 1 ; j < nums.size() ; j ++){
-                //cout << nums[j] - nums[i] << endl;
-                dis[nums[j]-nums[i]] ++;
-            }
-
-        int index = 0;
-        for(int i = 0 ; i < 1000000 ; i ++){
-            index += dis[i];
-            if(k <= index)
-                return i;
+        int l = 0, r = nums.back() - nums[0];
+        while(l < r){
+            int d = (l + r) / 2;
+            if(dis_cnt_less_than_or_equal_to(n, nums, d) >= k) r = d;
+            else l = d + 1;
         }
+        return l;
+    }
+
+private:
+    int dis_cnt_less_than_or_equal_to(int n, const vector<int>& nums, int d){
 
-        return -1;
+        int cnt = 0;
+        for(int i = 0; i < n; i ++){
+            auto iter = upper_bound(nums.begin(), nums.end(), nums[i] + d);
+            cnt += iter - nums.begin() - i - 1;
+        }
+        return cnt;
     }
 };
 
+
 int main() {
 
-    int nums1[] = {1, 3, 1};
-    int k1 = 1;
-    vector<int> vec1(nums1, nums1 + sizeof(nums1)/sizeof(int));
-    cout << Solution().smallestDistancePair(vec1, k1) << endl;
+    vector<int> nums1 = {1, 3, 1};
+    cout << Solution().smallestDistancePair(nums1, 1) << endl;
     // 0
 
-    // ---
+    vector<int> nums2 = {1, 1, 1};
+    cout << Solution().smallestDistancePair(nums2, 2) << endl;
+    // 0
 
-    int nums2[] = {1, 6, 1};
-    int k2 = 3;
-    vector<int> vec2(nums2, nums2 + sizeof(nums2)/sizeof(int));
-    cout << Solution().smallestDistancePair(vec2, k2) << endl;
+    vector<int> nums3 = {1, 6, 1};
+    cout << Solution().smallestDistancePair(nums3, 3) << endl;
     // 5
 
     return 0;
diff --git a/readme.md b/readme.md
@@ -723,7 +723,7 @@ email: [liuyubobobo@gmail.com](mailto:liuyubobobo@gmail.com)
 | 716 | [Max Stack](https://leetcode.com/problems/max-stack/description/) | [solution](https://leetcode.com/problems/max-stack/solution/) | [C++](0501-1000/0716-Max-Stack/cpp-0716/) | | |
 | 717 | [1-bit and 2-bit Characters](https://leetcode.com/problems/1-bit-and-2-bit-characters/description/) | | [C++](0501-1000/0717-1-bit-and-2-bit-Characters/cpp-0717/) | | |
 | 718 | [Maximum Length of Repeated Subarray](https://leetcode.com/problems/maximum-length-of-repeated-subarray/description/) | [缺：Rolling Hash] | [C++](0501-1000/0718-Maximum-Length-of-Repeated-Subarray/cpp-0718/) | | |
-| 719 | [Find K-th Smallest Pair Distance](https://leetcode.com/problems/find-k-th-smallest-pair-distance/description/) | [缺：二分搜索] | [C++](0501-1000/0719-Find-K-th-Smallest-Pair-Distance/cpp-0719/) | | |
+| 719 | [Find K-th Smallest Pair Distance](https://leetcode.com/problems/find-k-th-smallest-pair-distance/description/) | [solution](https://leetcode.com/problems/find-k-th-smallest-pair-distance/solution/) | [C++](0501-1000/0719-Find-K-th-Smallest-Pair-Distance/cpp-0719/) | | |
 | 720 | [Longest Word in Dictionary](https://leetcode.com/problems/longest-word-in-dictionary/description/) | [solution](https://leetcode.com/problems/longest-word-in-dictionary/solution/) | [C++](0501-1000/0720-Longest-Word-in-Dictionary/cpp-0720/) | | |
 | 721 | [Accounts Merge](https://leetcode.com/problems/accounts-merge/description/) | [solution](https://leetcode.com/problems/accounts-merge/solution/) | [C++](0501-1000/0721-Accounts-Merge/cpp-0721/) | | |
 | 722 | [Remove Comments](https://leetcode.com/problems/remove-comments/description/) | [solution](https://leetcode.com/problems/remove-comments/solution/) | [C++](0501-1000/0722-Remove-Comments/cpp-0722/) | | |
