การนำฟังก์ชัน f(x) = ax² + bx + c ไปประยุกต์กับอาร์เรย์ที่เรียงแล้วใน JavaScript

ปัญหา

กำหนด sorted array และฟังก์ชัน quadratic f(x) = ax² + bx + c ให้ apply f(x) กับทุก element แล้วคืน sorted array ของผลลัพธ์

ตัวอย่าง

arr = [-8, -3, -1, 5, 7, 9], a=1, b=4, c=7
output: [4, 4, 39, 52, 84, 124]

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

const arr = [-8, -3, -1, 5, 7, 9];
const a = 1;
const b = 4;
const c = 7;

const applyFunction = (arr = [], a = 1, b = 1, c = 1) => {
  const apply = (num, a, b, c) => {
    const res = (a * (num * num)) + (b * num) + (c);
    return res;
  };
  const result = arr.map(el => apply(el, a, b, c));
  result.sort((a, b) => a - b);
  return result;
};

console.log(applyFunction(arr, a, b, c));

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

Map ทุก element ผ่าน f(x) แล้ว sort ผลลัพธ์

Time: O(n log n) เนื่องจาก sort

Optimization: O(n) Two Pointers

เนื่องจาก f(x) เป็น parabola หาก a > 0 ค่าสูงสุดอยู่ปลายทั้งสอง หาก a < 0 ค่าต่ำสุดอยู่ปลาย

ใช้ two pointers จากปลายทั้งสอง เลือกค่าที่มากกว่า (a>0) หรือน้อยกว่า (a<0) ใส่ result จากท้ายหรือหน้า

const sortTransformedArray = (nums, a, b, c) => {
  const f = x => a*x*x + b*x + c;
  let left = 0, right = nums.length - 1;
  const res = new Array(nums.length);
  let idx = a >= 0 ? right : left;
  while (left <= right) {
    const lVal = f(nums[left]), rVal = f(nums[right]);
    if (a >= 0) {
      if (lVal > rVal) res[idx--] = lVal, left++;
      else res[idx--] = rVal, right--;
    } else {
      if (lVal < rVal) res[idx++] = lVal, left++;
      else res[idx++] = rVal, right--;
    }
  }
  return res;
};

ผลลัพธ์

[4, 4, 39, 52, 84, 124]