diff options
-rw-r--r-- | find_k_small_pair_dist.c | 34 | ||||
-rw-r--r-- | find_k_small_pair_dist.py | 44 |
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)) |