aboutsummaryrefslogtreecommitdiff
path: root/find_k_small_pair_dist.c
diff options
context:
space:
mode:
Diffstat (limited to 'find_k_small_pair_dist.c')
-rw-r--r--find_k_small_pair_dist.c34
1 files changed, 34 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
+}