diff options
-rw-r--r-- | smallest_range_convering_elem_k.c | 67 | ||||
-rw-r--r-- | smallest_range_convering_elem_k.py | 37 |
2 files changed, 104 insertions, 0 deletions
diff --git a/smallest_range_convering_elem_k.c b/smallest_range_convering_elem_k.c new file mode 100644 index 0000000..3cb4a3d --- /dev/null +++ b/smallest_range_convering_elem_k.c @@ -0,0 +1,67 @@ +// 632. Smallest Range Covering Elements from K Lists +#include "leetcode.h" + +/* + * you have 'k' lists of sorted integers in non decreasing order. find the + * smallest range that includes at least one number from each of the 'k' lists. + * we define the range '[a, b]' is smaller than the range '[c, d]' if 'b - a < d + * - c' or 'a < c' if 'b - a == d - c' + */ + +int cmp(const void *a, const void *b) { return (*(int *)a - *(int *)b); } + +int *smallestRange(int **nums, int numsSize, int *numsColSize, + int *returnSize) { + int n = 0, idx = 0; + for (int i = 0; i < numsSize; i++) + n += numsColSize[i]; + int *data = (int *)calloc(n, sizeof(int)); + for (int i = 0; i < numsSize; i++) + for (int j = 0; j < numsColSize[i]; j++) + data[idx++] = nums[i][j] * 4096 | i; + qsort(data, n, sizeof(int), cmp); + int *ans = (int *)calloc(2, sizeof(int)); + int left = 0, right = 0, list_cnt = 0, + min_range = (data[n - 1] >> 12) - (data[0] >> 1); + ans[0] = data[0] >> 12; + ans[1] = data[n - 1] >> 12; + idx = 0; + memset(numsColSize, 0, numsSize * sizeof(int)); + while (right < n) { + int list_idx = data[right++] & 0xFFF; + numsColSize[list_idx]++; + if (numsColSize[list_idx] == 1) { + list_cnt++; + while (list_cnt == numsSize) { + int diff = (data[right - 1] >> 12) - (data[left] >> 12); + if (diff < min_range) { + ans[0] = data[left] >> 12; + ans[1] = data[right - 1] >> 12; + min_range = diff; + } + list_idx = data[left++] & 0xFFF; + numsColSize[list_idx]--; + if (!numsColSize[list_idx]) + list_cnt--; + } + } + } + *returnSize = 2; + free(data); + return ans; +} + +int main() { + int n1[3][5] = {{4, 10, 15, 24, 26}, {0, 9, 12, 20}, {5, 18, 22, 30}}, + ncs1 = 3, rs1; + int n2[3][3] = {{1, 2, 3}, {1, 2, 3}, {1, 2, 3}}, ncs2 = 3, rs2; + int *sr1 = smallestRange((int **)n1, ARRAY_SIZE(n1), &ncs1, &rs1); + int *sr2 = smallestRange((int **)n2, ARRAY_SIZE(n2), &ncs2, &rs2); + for (int i = 0; i < rs1; i++) + printf("%d ", sr1[i]); // expect: 20 24 + printf("\n"); + for (int i = 0; i < rs2; i++) + printf("%d ", sr2[i]); // expect: 1 1 + printf("\n"); + free(sr1), free(sr2); +} diff --git a/smallest_range_convering_elem_k.py b/smallest_range_convering_elem_k.py new file mode 100644 index 0000000..35b0e77 --- /dev/null +++ b/smallest_range_convering_elem_k.py @@ -0,0 +1,37 @@ +# 632. Smallest Range Covering Elements from K Lists +import heapq + +""" +you have 'k' lists of sorted integers in non decreasing order. find the +smallest range that includes at least one number from each of the 'k' lists. +we define the range '[a, b]' is smaller than the range '[c, d]' if 'b - a < d +- c' or 'a < c' if 'b - a == d - c' +""" + + +class Solution(object): + def smallestRange(self, nums): + """ + :type nums: List[List[int]] + :rtype: List[int] + """ + pq = [(row[0], i, 0) for i, row in enumerate(nums)] + ans = -1e9, 1e9 + right = max(row[0] for row in nums) + while pq: + left, i, j = heapq.heappop(pq) + if right - left < ans[1] - ans[0]: + ans = left, right + if j + 1 == len(nums[i]): + return ans + v = nums[i][j + 1] + right = max(right, v) + heapq.heappush(pq, (v, i, j + 1)) + + +if __name__ == "__main__": + obj = Solution() + print( + obj.smallestRange(nums=[[4, 10, 15, 24, 26], [0, 9, 12, 20], [5, 18, 22, 30]]) + ) + print(obj.smallestRange(nums=[[1, 2, 3], [1, 2, 3], [1, 2, 3]])) |