diff options
Diffstat (limited to 'find_k_small_pair_dist.c')
-rw-r--r-- | find_k_small_pair_dist.c | 34 |
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 +} |