หาตัวเลขสูงสุดจากสองอาร์เรย์ใน JavaScript

ปัญหา

เราต้องเขียนฟังก์ชัน JavaScript ที่รับอาร์เรย์ของตัวเลขหลักเดียว 2 อาร์เรย์ คือ arr1 และ arr2 แทนตัวเลขสองจำนวน อาร์กิวเมนต์ที่สามคือตัวเลข num (num <= ความยาว arr1 + ความยาว arr2)

ฟังก์ชันควรคืนอาร์เรย์ใหม่ของตัวเลขหลักเดียว ความยาว num ซึ่งแทนตัวเลขที่ใหญ่ที่สุดที่สร้างได้จากสมาชิกของทั้งสองอาร์เรย์ โดยเงื่อนไขคือต้องรักษาลำดับสัมพัทธ์ของสมาชิกจากอาร์เรย์เดิม

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

const arr1 = [1, 3, 4, 5, 6]; 
const arr2 = [9, 1, 2, 5, 8, 3]; 
const num = 4;

ผลลัพธ์ควรเป็น

const output = [9, 8, 6, 3];

ตัวอย่างโค้ด

const arr1 = [1, 3, 4, 5, 6]; 
const arr2 = [9, 1, 2, 5, 8, 3]; 
const num = 4; 
const maxArray = (arr1 = [], arr2 = [], num) => {
  const map = new Map();
  const match = (a, b, num) => {
    if (map.has(a + ',' + b + ',' + num)) {
      return map.get(a + ',' + b + ',' + num);
    }
    let output = [];
    while(num > 0) {
      let maxa = -Infinity;
      let maxai = 0;
      let maxb = -Infinity;
      let maxbi = 0;
      for(let i = a; i < arr1.length && arr1.length + arr2.length - (i + b) >= num; i++) {
        if (arr1[i] > maxa) {
          maxa = arr1[i];
          maxai = i;
        }
      }
      for(let i = b; i < arr2.length && arr1.length + arr2.length - (a + i) >= num; i++) {
        if (arr2[i] > maxb) {
          maxb = arr2[i];
          maxbi = i;
        }
      }
      if (maxa === maxb) {
        output.push(maxa);
        let ca = map.get(a+','+(maxbi+1)+','+(num-1)) || match(a, maxbi+1, num-1);
        let cb = map.get((maxai+1)+','+b+','+(num-1)) || match(maxai+1,b,num-1);
        map.set(a+','+(maxbi+1)+','+(num-1), ca);
        map.set((maxai+1)+','+b+','+(num-1), cb);
        if (ca.join('') > cb.join('')) {
          return [...output, ...ca];
        } else {
          return [...output, ...cb];
        }
      } else if (maxa > maxb) {
        output.push(maxa);
        a = maxai + 1;
      } else {
        output.push(maxb);
        b = maxbi + 1;
      }
      num--;
    }
    map.set(a + ',' + b + ',' + num, output);
    return output;
  }
  return match(0, 0, num);
};
console.log(maxArray(arr1, arr2, num));

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

ขั้นตอนที่ทำคือ

• ใช้ for-loop จนกว่าจะเหลือ num ที่อนุญาต

• ถ้า arr1 มีตัวเลขมากกว่า arr2 เราจะใช้ตัวเลขของ arr1 ก่อน มิฉะนั้นใช้ arr2

• เมื่อ arr1 และ arr2 มีตัวเลขเท่ากันจนกว่า for-loop จะสิ้นสุด เราใช้ recursion เปรียบเทียบค่าทั้งสอง และเลือกตัวที่ใหญ่กว่า

ผลลัพธ์

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

[ 9, 8, 6, 3 ]