632. Smallest Range Covering Elements from K Lists

[Tcdian]

632. Smallest Range Covering Elements from K Lists

你有 k 个升序排列的整数数组。找到一个最小区间，使得 k 个列表中的每个列表至少有一个数包含在其中。

我们定义如果 b-a < d-c 或者在 b-a == d-c 时 a < c，则区间 [a,b] 比 [c,d] 小。

Example

Input: [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
Output: [20,24]
Explanation: 
List 1: [4, 10, 15, 24,26], 24 is in range [20,24].
List 2: [0, 9, 12, 20], 20 is in range [20,24].
List 3: [5, 18, 22, 30], 22 is in range [20,24].

Note

• 给定的列表可能包含重复元素，所以在这里升序表示 >= 。
• 1 <= k <= 3500
• -105 <= 元素的值 <= 105

[Tcdian]

Solution

• JavaScript Solution

/**
 * @param {number[][]} nums
 * @return {number[]}
 */
var smallestRange = function(nums) {
    const groups = nums.map((group, groupIndex) => group.map((num) => [num, groupIndex]));
    const flatten = groups.reduce((prev, group) => [...prev, ...group]);
    const sorted = flatten.sort(([a], [b]) => a - b);
    const groupCounts = new Array(groups.length).fill(0);
    let includedGroupCount = 0;
    let result = [sorted[0][0], sorted[sorted.length - 1][0]];
    for (let left = 0, right = 0; right < sorted.length; right++) {
        if (groupCounts[sorted[right][1]] === 0) {
            includedGroupCount++;
        }
        groupCounts[sorted[right][1]] += 1;
        while(groupCounts[sorted[left][1]] > 1) {
            groupCounts[sorted[left][1]]--;
            left++;
        }
        if (includedGroupCount === groups.length && sorted[right][0] - sorted[left][0] < result[1] - result[0]) {
            result = [sorted[left][0], sorted[right][0]];
        }
    }
    return result;
};

• TypeScript Solution

function smallestRange(nums: number[][]): number[] {
    const groups: [number, number][][] = nums.map((group, groupIndex) => group.map((num) => [num, groupIndex]));
    const flatten = groups.reduce((prev, group) => [...prev, ...group]);
    const sorted = flatten.sort(([a], [b]) => a - b);
    const groupCounts = new Array(groups.length).fill(0);
    let includedGroupCount = 0;
    let result: [number, number] = [sorted[0][0], sorted[sorted.length - 1][0]];
    for (let left = 0, right = 0; right < sorted.length; right++) {
        if (groupCounts[sorted[right][1]] === 0) {
            includedGroupCount++;
        }
        groupCounts[sorted[right][1]] += 1;
        while(groupCounts[sorted[left][1]] > 1) {
            groupCounts[sorted[left][1]]--;
            left++;
        }
        if (includedGroupCount === groups.length && sorted[right][0] - sorted[left][0] < result[1] - result[0]) {
            result = [sorted[left][0], sorted[right][0]];
        }
    }
    return result;
};