aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--find_k_small_pair_dist.c34
-rw-r--r--find_k_small_pair_dist.py44
2 files changed, 78 insertions, 0 deletions
diff --git a/find_k_small_pair_dist.c b/find_k_small_pair_dist.c
new file mode 100644
index 0000000..aede5c6
--- /dev/null
+++ b/find_k_small_pair_dist.c
@@ -0,0 +1,34 @@
+// 719. Find K-th Smallest Pair Distance
+#include "leetcode.h"
+
+/*
+ * the distance of a pair of integers 'a' and 'b' is defined as the absolute
+ * different between 'a' and 'b'. given an integer array 'nums' and an integer
+ * 'k', return the smallest k'th distance among all the pairs 'nums[i]' and
+ * 'nums[j]' where '0 <= i < j < nums.len'.
+ */
+
+int cmp(const void *a, const void *b) { return (*(int *)a - *(int *)b); }
+
+int smallestDistancePair(int *nums, int numsSize, int k) {
+ qsort(nums, numsSize, sizeof(int), cmp);
+ int n = nums[numsSize - 1] + 1, ans;
+ int *hash = (int *)calloc(n, sizeof(int));
+ for (int i = 0; i < numsSize - 1; i++)
+ for (int j = i + 1; j < numsSize; j++)
+ hash[nums[j] - nums[i]]++;
+ for (ans = 0; ans < n; ans++)
+ if (hash[ans]) {
+ k -= hash[ans];
+ if (k <= 0)
+ break;
+ }
+ return ans;
+}
+
+int main() {
+ int n1[] = {1, 3, 1}, n2[] = {1, 1, 1}, n3[] = {1, 6, 1};
+ printf("%d\n", smallestDistancePair(n1, ARRAY_SIZE(n1), 1)); // expect: 0
+ printf("%d\n", smallestDistancePair(n2, ARRAY_SIZE(n2), 2)); // expect: 0
+ printf("%d\n", smallestDistancePair(n3, ARRAY_SIZE(n3), 3)); // expect: 5
+}
diff --git a/find_k_small_pair_dist.py b/find_k_small_pair_dist.py
new file mode 100644
index 0000000..b49157d
--- /dev/null
+++ b/find_k_small_pair_dist.py
@@ -0,0 +1,44 @@
+# 719. Find K-th Smallest Pair Distance
+
+"""
+the distance of a pair of integers 'a' and 'b' is defined as the absolute
+different between 'a' and 'b'. given an integer array 'nums' and an integer
+'k', return the smallest k'th distance among all the pairs 'nums[i]' and
+'nums[j]' where '0 <= i < j < nums.len'.
+"""
+
+
+class Solution(object):
+ def smallestDistancePair(self, nums, k):
+ """
+ :type nums: List[int]
+ :type k: int
+ :rtype: int
+ """
+
+ def enough(dist):
+ cnt, i, j = 0, 0, 0
+ while i < n or j < n:
+ while j < n and nums[j] - nums[i] <= dist:
+ j += 1
+ cnt += j - i - 1
+ i += 1
+ return cnt >= k
+
+ nums.sort()
+ n = len(nums)
+ left, right = 0, nums[-1] - nums[0]
+ while left < right:
+ mid = left + (right - left) // 2
+ if not enough(mid):
+ left = mid + 1
+ else:
+ left = mid
+ return left
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.smallestDistancePair(nums=[1, 3, 1], k=1))
+ print(obj.smallestDistancePair(nums=[1, 1, 1], k=2))
+ print(obj.smallestDistancePair(nums=[1, 6, 1], k=3))