Phần tử nhỏ nhất thứ n trong mảng 2-D được sắp xếp trong JavaScript

Vấn đề

Giả sử, chúng ta có một mảng các mảng Số được sắp xếp (sắp xếp theo thứ tự tăng dần) như thế này -

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

Chúng tôi được yêu cầu viết một hàm JavaScript nhận vào một mảng như đối số đầu tiên và một Số nguyên duy nhất, num, làm đối số thứ hai.

Hàm của chúng ta phải trả về phần tử nhỏ nhất thứ số tồn tại trong mảng arr.

Ví dụ:nếu đầu vào của hàm là -

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

Đầu ra

Sau đó, đầu ra phải 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ụ

Mã cho điều này sẽ là -

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 ở đây là -

Khi chúng tôi có một mảng 2d được sắp xếp thông thường, chúng tôi sử dụng một loạt các chỉ mục để tìm mục tiêu của mình, ví dụ:

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

nếu mục tiêu lớn hơn số ở giữa chỉ mục, thì chúng tôi tìm kiếm phần bên phải, nếu nó nhỏ hơn, chúng tôi tìm kiếm bên trái.

Tuy nhiên, trong mảng được sắp xếp arr 2d này, không thể tìm thấy chỉ số giữa như vậy. Trực giác ở đây là sử dụng một loạt các số để kiểm tra đối với k của chúng ta. Chúng tôi biết số đầu tiên là số nhỏ nhất và số cuối cùng là số lớn nhất, điều này có nghĩa là số mục tiêu của chúng tôi phải nằm ở giữa. Chúng ta có thể sử dụng hai số đó làm giá trị thấp và cao, đồng thời đặt giá trị trung bình của chúng ta là số ở giữa và kiểm tra xem có bao nhiêu số trong arr nhỏ hơn số đó và điều chỉnh thấp và cao cho phù hợp.

Khi chúng ta nhận được chính xác k số, chúng ta biết rằng chúng ta đã tìm thấy câu trả lời của mình. Phần cực kỳ khó khăn ở đây là chỉ cần nhìn vào cách chúng ta tính toán giữa, rất nhiều lần con số chúng ta đang thử nghiệm thậm chí có thể không ở trong arr, bởi vì cuối cùng, những con số chúng ta đang sử dụng chỉ là những con số tùy ý.

Để giải thích điều này, chúng ta cần tưởng tượng rằng chương trình của chúng ta đang ở giai đoạn mà mức thấp và mức cao gần như chạm vào nhau. nếu chúng tôi đếm số lượng ít hơn dự kiến, chúng tôi sẽ đặt low =mid + 1, điều này có khả năng chỉ tăng số giữa của chúng tôi lên 1. Và bằng cách tăng số giữa của chúng tôi 1 lên 1, chúng tôi có thể đảm bảo các số được bao gồm trong arr.

Đầu ra

Đầu ra trong bảng điều khiển sẽ là -