https://www.lintcode.com/problem/smallest-range/description
有k個升序排列的數(shù)組篮绰，尋找一個最小范圍，使每個數(shù)組中至少有一個元素被包含跌穗。
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了贿衍，主要原因還是內(nèi)部的排序浪默，如果能用O(1)的時間復(fù)雜度來維持一個最大最小值來替換排序算法應(yīng)該就能AC了牡直。
看了一下解出來的算法，用了最小堆浴鸿，JAVA應(yīng)該可以用SortedMap來解決井氢。
數(shù)據(jù)結(jié)構(gòu)的怨念
