整数を昇順に並べたk個の配列があります．k個のリストのそれぞれが少なくとも1つの数を含むような最小の区間を求めなさい．
区間[a,b]が[c,d]より小さいのは、b-a < d-cのとき、または、b-a == d-cのとき、a < cのときです。
:
:[[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
: [20,24]
:
リスト 1：[4, 10, 15, 24, 26]，24 区間 [20,24]
リスト2[0, 9, 12, 20]，20 区間 [20,24]
リスト3[5, 18, 22, 30]，22 区間 [20,24]
注目:
- 指定されたリストには重複した要素が含まれる可能性があるため、ここでは昇順で >= を示します。
- 1 <= k <= 0530
- -105 <= 要素の値 <= 501
推論
ただ、この質問を見て本当にアイデアを持っていない、最小カバレッジの部分文字列を完了するために行く最初の問題の公式解答を読む：more-011: 最小被覆部分文字列
振り返ってみれば、その思考プロセスはもっと明白です：
- nums の行列を順序付き配列にマージし、各要素の元となる行の数を記録します。
- すべての行をカバーする最終的な数値区間
ろんりご
- 値と行数を記録するには、配列 {index: 行数, value: 値} を使用します。
- 新しいソート配列dp
- left，right新しい配列ポインタ
- マップはマッチする行のインデックス、つまり行数を記録します。
- Rleft，Rright終了間隔
/**
* @param {number[][]} nums
* @return {number[]}
*/
var smallestRange = function(nums) {
let dp = [],
map = new Map(),
left = 0,
right = 0,
Rleft = -Number.MAX_VALUE, // 結果区間の左インデックス
Rright = -1, // 結果区間の右インデックス
type = 0; // 区間内の数値ソースの行の種類
// 2Dマッピング配列を生成する dp 行マッピングマップ
for (let i = 0; i < nums.length; i++) {
map.set(i, 0);
for (let j = 0; j < nums[i].length; j++) {
dp.push({ index: i, value: nums[i][j] })
}
}
// dp
dp.sort((a, b) => a.value - b.value);
//
while (right < dp.length) {
let Rindex = dp[right].index, // ポインタがある番号のソース行
Rvalue = dp[right].value, // ポインタが位置する番号
RMvalue = map.get(Rindex) // 書き換える区間の桁数
// 区間追加 新しい行に由来する 行タイプ+1
if (RMvalue === 0) ++type
// 追加された桁数を記録する
map.set(Rindex, ++RMvalue)
// ソース行はすべての行を含み、マップサイズに等しい。
while (type === map.size && left <= right) {
let Lindex = dp[left].index,
Lvalue = dp[left].value,
LMvalue = map.get(Lindex);
// 新しい間隔が小さければ、それを使う
if (Rvalue - Lvalue < Rright - Rleft) {
Rleft = Lvalue
Rright = Rvalue
}
// 番号を破棄し、マップレコードをマイナス1する
map.set(Lindex, --LMvalue)
// 桁数不足のカウントが0の場合、ソース行に区間内の桁数がないことを示し、行数を減らす
if (LMvalue === 0) --type
// 区間を右にシフトさせる
left++
}
// 右区間は右にシフトしている
right++
}
return [Rleft, Rright]
};
ブログ： リトル・ブッキー・ブログ
出版：The Pit's Little Bookie
