aboutsummaryrefslogtreecommitdiff
path: root/find_k_small_pair_dist.c
blob: aede5c60f15caac0b4abb8d4374a96c6956611e4 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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
}