องค์ประกอบที่เล็กที่สุดอันดับที่ N ในอาร์เรย์ 2-D ที่จัดเรียงใน JavaScript

ปัญหา

สมมติว่าเรามีอาร์เรย์ของอาร์เรย์ของตัวเลข (เรียงตามลำดับเพิ่มขึ้น) แบบนี้ -

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

เราจำเป็นต้องเขียนฟังก์ชัน JavaScript ที่รับอาร์เรย์เช่นอาร์กิวเมนต์แรกและจำนวนเต็มเดียว num เป็นอาร์กิวเมนต์ที่สอง

ฟังก์ชันของเราควรจะส่งคืนองค์ประกอบที่น้อยที่สุดที่มีอยู่ในอาร์เรย์ arr

ตัวอย่างเช่น หากอินพุตของฟังก์ชันคือ −

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

ผลลัพธ์

จากนั้นผลลัพธ์ควรเป็น −

const output = 11;

คำอธิบายผลลัพธ์:

11 เป็นองค์ประกอบที่เล็กที่สุดอันดับห้าในเมทริกซ์

ตัวอย่าง

รหัสสำหรับสิ่งนี้จะเป็น −

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

คำอธิบายโค้ด:

แนวคิดที่นี่คือ −

เมื่อเรามีอาร์เรย์ 2d ที่จัดเรียงแบบปกติ เราจะใช้ช่วงของดัชนีเพื่อค้นหาเป้าหมายของเรา ตัวอย่างเช่น

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

หากเป้าหมายมากกว่าตัวเลขที่ดัชนีกลาง เราจะค้นหาส่วนที่ถูกต้อง หากน้อยกว่า เราจะค้นหาทางซ้าย

อย่างไรก็ตาม ในอาร์เรย์ที่จัดเรียง 2d arr นี้ เป็นไปไม่ได้ที่จะหาดัชนีกลางเช่นนี้ สัญชาตญาณในที่นี้คือการใช้ช่วงของตัวเลขเพื่อทดสอบกับ k ของเรา เรารู้ว่าจำนวนแรกมีค่าน้อยที่สุดและจำนวนสุดท้ายมีค่ามากที่สุด ซึ่งหมายความว่าจำนวนเป้าหมายของเราต้องอยู่ระหว่างนั้น เราสามารถใช้ตัวเลขสองตัวนี้เป็นค่าต่ำและสูงได้ และตั้งค่าให้กลางเป็นตัวเลขที่อยู่ระหว่างนั้น และตรวจดูว่าตัวเลขใน arr น้อยกว่าจำนวนนั้นจำนวนเท่าใด แล้วปรับค่าต่ำและสูงตามลำดับ

เมื่อเราได้ตัวเลข k ครบแล้ว เรารู้ว่าเราพบคำตอบแล้ว ส่วนที่ยุ่งยากอย่างยิ่งในที่นี้คือเพียงแค่ดูว่าเราคำนวณค่ากลางอย่างไร หลายครั้งที่ตัวเลขที่เรากำลังทดสอบอาจไม่อยู่ใน arr เพราะในท้ายที่สุด ตัวเลขที่เราใช้อยู่เป็นเพียงตัวเลขทั่วไป

เพื่ออธิบายสิ่งนี้ เราต้องจินตนาการว่าโปรแกรมของเราอยู่ในขั้นที่ต่ำและสูงเกือบจะตีกัน หากเรานับจำนวนน้อยกว่าที่คาดไว้ เราจะตั้งค่า low=mid+1 ซึ่งอาจทำให้เพิ่มค่ากลางของเราทีละ 1 และด้วยการเพิ่มค่ากลางของเรา 1 ต่อ 1 เราจึงมั่นใจได้ว่าตัวเลขนั้นรวมอยู่ใน arr แล้ว

ผลลัพธ์

ผลลัพธ์ในคอนโซลจะเป็น -