การแบ่งอาร์เรย์เป็นสองกลุ่มที่มีค่าเฉลี่ยเท่ากันใน JavaScript

บทความนี้สาธิตการตรวจสอบว่าสามารถแบ่งอาร์เรย์เป็น 2 กลุ่มที่มี average เท่ากันได้หรือไม่

ตัวอย่าง

arr = [6, 3, 2, 8, 1, 5, 7, 4]
group1: [8,1,5,4] avg=4.5, group2: [6,3,2,7] avg=4.5 -> true

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

const arr = [6, 3, 2, 8, 1, 5, 7, 4];

const canHaveEqualAveragePartition = (arr = []) => {
  const sum = arr.reduce((acc, val) => acc + val);
  const array = Array(sum + 1).fill(false).map(() =>
    Array(arr.length + 1).fill(false)
  );
  array[0][0] = true;
  for (let i = 0; i < arr.length; ++i) {
    for (let j = sum - arr[i]; j >= 0; --j) {
      for (let k = arr.length - 2; k >= 0; --k) {
        if (array[j][k]) {
          array[j + arr[i]][k + 1] = true;
          if ((j + arr[i]) * (arr.length - k - 1) == (sum - j - arr[i]) * (k + 1)) {
            return true;
          }
        }
      }
    }
  }
  return false;
};

console.log(canHaveEqualAveragePartition(arr));

ผลลัพธ์

true

คำอธิบาย

Dynamic Programming: array[sum][count] = สามารถสร้าง sum ด้วย count elements ได้หรือไม่

เงื่อนไข average เท่ากัน: sum1/count1 = sum2/count2 = totalSum/totalCount

กลายเป็น sum1 * (n - count1) = (totalSum - sum1) * count1

Time: O(n * sum * n) = O(n² * sum), Space: O(n * sum)