JavaScriptでソートされた2次元配列のN番目に小さい要素

---

問題

次のように、数値の配列の並べ替えられた配列（昇順で並べ替えられた）があるとします-

const arr = [
   [ 1, 5, 9],
   [10, 11, 13],
   [12, 13, 15]
];

最初の引数として1つの配列を取り、2番目の引数として単一の整数numを取り入れるJavaScript関数を作成する必要があります。

この関数は、配列arrに存在する最小の要素を返すことになっています。

たとえば、関数への入力が-

の場合

const arr = [
   [ 1, 5, 9],
   [10, 11, 13],
   [12, 13, 15]
];
const num = 5;

出力

その場合、出力は-

になります。

const output = 11;

出力の説明：

11は、マトリックス内で5番目に小さい要素です。

例

このためのコードは-

になります

const arr = [
   [ 1, 5, 9],
   [10, 11, 13],
   [12, 13, 15]
];
const num = 5;
const kthSmallest = (arr = [], num = 1) => {
   let low = arr[0][0]
   let high = arr[arr.length-1][arr[0].length-1] + 1;
   while (low < high) {
      let mid = low + Math.floor((high-low)/2);
      let count = 0;
      for (let i = 0;i<arr.length;i++) {
         for (let j=0;j<arr.length;j++) {
            if (arr[i][j] <= mid) count++;
            else break;
         }
      }
   if (count < num) low = mid+1;
      else high = mid;
   }
   return low
};
console.log(kthSmallest(arr, num));

コードの説明：

ここでの考え方は-

通常の並べ替えられた2次元配列がある場合、たとえば

などのインデックスの範囲を使用してターゲットを検索します。

low = 0, high = length-1, mid = (low+high)/2

ターゲットがインデックスmidの数値よりも大きい場合は右側を検索し、小さい場合は左側を検索します。

ただし、この2d arrでソートされた配列では、そのような中間インデックスを見つけることはできません。ここでの直感は、kに対してテストするために数値の範囲を使用することです。最初の数字が最小で最後の数字が最大であることがわかっています。これは、ターゲット番号がその中間にある必要があることを意味します。これらの2つの数値を下限と上限として使用し、中間をその中間の数値に設定し、arr内の数値のうち、その数値よりも小さい数値を確認し、それに応じて下限と上限を調整できます。

正確にk個の数値を取得すると、答えが見つかったことがわかります。ここで非常に注意が必要なのは、中間の計算方法を見るだけでは、多くの場合、テストしている数値がarrに含まれていない可能性があることです。これは、最終的に、使用している数値が単なる任意の数値であるためです。

これを説明するために、私たちのプログラムは、低値と高値がほぼ互いにぶつかり合う段階にあることを想像する必要があります。予想よりも少ない数をカウントした場合は、low =mid + 1に設定します。これにより、midが1増える可能性があります。また、mid 1を1ずつ増やすことで、その数がarrに含まれるようにすることができます。

>

出力

コンソールの出力は-

になります

11