Phần tử nhỏ thứ N trong mảng 2D đã sắp xếp trong JavaScript

Mô tả vấn đề

Giả sử chúng ta có một mảng các mảng số (đã sắp xếp tăng dần) như sau:

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

Chúng ta cần viết một hàm JavaScript nhận vào mảng như vậy làm đối số đầu tiên và một số nguyên num làm đối số thứ hai. Hàm phải trả về phần tử nhỏ thứ num tồn tại trong mảng arr.

Ví dụ, nếu đầu vào là:

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

Thì đầu ra nên là:

const output = 11;

Giải thích đầu ra

11 là phần tử nhỏ thứ năm trong ma trận.

Ví dụ minh họa

Mã thực hiện (sử dụng tìm kiếm nhị phân trên khoảng giá trị):

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));

Giải thích mã

Ý tưởng là sử dụng tìm kiếm nhị phân trên khoảng giá trị thay vì chỉ số. Chúng ta biết số đầu tiên là nhỏ nhất và số cuối là lớn nhất, nên phần tử nhỏ thứ k phải nằm giữa chúng. Ta dùng low/high là giá trị min/max, mid là giá trị giữa, đếm số phần tử <= mid để điều chỉnh low/high.

Phần khó là mid có thể không nằm trong mảng. Khi low và high gần nhau, việc tăng mid lên 1 đơn vị đảm bảo cuối cùng ta sẽ tìm thấy giá trị thực tế trong mảng.

Đầu ra

Kết quả trong console sẽ là:

11