https://www.lintcode.com/problem/smallest-range/description
有k个升序排列的数组，寻找一个最小范围，使每个数组中至少有一个元素被包含。
const smallestRange = function (nums) {
// write your code here
var arr = []
nums.forEach((x, i) => {
x.forEach(_x => {
arr.push([i, _x])
})
})
arr.sort((a, b) => {
return a[1] - b[1];
});
let total = nums.length;
let tmp;
let interval = 0;
if (arr.length === nums.length) {
return [arr[0][1], arr[nums.length - 1][1]]
}
let map = new Map();
for (let i = 0; i < arr.length; i++) {
map.set(arr[i][0], arr[i][1]);
if (map.size === total) {
let list = Array.from(map);
list.sort((a, b) => a[1] - b[1]);
let tInt = list[list.length - 1][1] - list[0][1];
if (tmp) {
if (interval > tInt) {
interval = tInt;
tmp = [list[0][1], list[list.length - 1][1]];
}
} else {
interval = tInt;
tmp = [list[0][1], list[list.length - 1][1]];
}
}
}
return tmp;
}
算法没什么问题，这边利用了Map的特性。
就是TLE了，主要原因还是内部的排序，如果能用O(1)的时间复杂度来维持一个最大最小值来替换排序算法应该就能AC了。
看了一下解出来的算法，用了最小堆，JAVA应该可以用SortedMap来解决。
数据结构的怨念
