遇到一个算法问题 js的 不知道怎么优化比较好？

Question

遇到一个算法问题 js的 不知道怎么优化比较好

const getPayList = (list: { name: string; pay: number }[]) => {

const total = list.reduce((prev, { pay }) => prev + pay, 0);
const average = Math.round((total / list.length) * 100);
const newList = list
  .map(({ pay, ...other }) => {
    return {
      needPay: average - pay * 100,
      pay: pay * 100,
      ...other,
    };
  })
  .sort(({ needPay: a }, { needPay: b }) => b - a);
const get = newList.filter(({ needPay }) => needPay < 0);
const give = newList.filter(({ needPay }) => needPay > 0);
const toPayRes = [];
let currentGiveIdx = 0;
const toPay = (item) => {
  if (currentGiveIdx >= give.length) return;
  const currentGive = give[currentGiveIdx];
  const { needPay } = currentGive;
  const total = needPay + item.needPay;
  if (total > 0) {
    give[currentGiveIdx].needPay = total;
    toPayRes.push(`${currentGive.name}转${Math.abs(item.needPay) / 100}给${item.name}`);
    item.needPay = 0;
  } else if (total === 0) {
    item.needPay = total;
    currentGiveIdx += 1;
    toPayRes.push(`${currentGive.name}转${currentGive.needPay / 100}给${item.name}`);
  } else {
    currentGiveIdx += 1;
    item.needPay = total;
    toPayRes.push(`${currentGive.name}转${currentGive.needPay / 100}给${item.name}`);
    toPay(item);
  }
};
get.forEach((item) => {
  toPay(item);
});

};

Answer 1

• js 新手，用自带的方法写烦了。。跑去学了下 lodash。第一次用，有不对的恳请指出
• 另外，由于没说清楚如何解决【无法绝对平均分账】问题，所以简单粗暴加了个判断
• 时间复杂度还是指数级。抛砖引玉，等大佬赏脸优化
• 只测试过几组数据，有错请提出

输入

[
    {name: '甲', pay: 1},
    {name: '甲', pay: 2},
    {name: '甲', pay: 3},
    {name: '甲', pay: 4},
    {name: '乙', pay: 5},
    {name: '丙', pay: 6},
    {name: '丁', pay: 7},
]

输出

乙支付2元给甲，丙支付1元给甲

js 代码

import _ from 'lodash';

const list = [
    {name: '甲', pay: 1},
    {name: '甲', pay: 2},
    {name: '甲', pay: 3},
    {name: '甲', pay: 4},
    {name: '乙', pay: 5},
    {name: '丙', pay: 6},
    {name: '丁', pay: 7},
];

function getPayList(list) {

    // 中间数据，每个人总付款表（单位：分）
    // 如：{"甲": 1000, "乙": 500, "丙": 600}
    let inter = _(list)
        .groupBy('name')
        .mapValues(v => _.sumBy(v, i => Math.round(i.pay * 100)));

    // 计算总消费、人群数、平均消费
    const total = inter.values().sum();
    const count = inter.size();
    const avg = total / count;

    // 下面的算法，要求能精确分账
    if (total % count) {
        throw new Error('暂不支持无法均摊的分账');
    }

    // 按每人应收回金额，从小到大排序，分成名字、金额数组
    // name: ['乙', '丙', '甲']
    // pay : [-200, -100, 300]
    let result = [];
    let [name, pay] = inter
        .map((val, key) => [key, val - avg])
        .sortBy(1)
        .unzip()
        .value();

    // 尝试找到 1、2、…… 人，使得他们之间能平账
    for (let size = 1; pay.length; ++size) {
        let idx = Array(size);

        function find(sum, dep) {
            if (dep + 1 < size) {
                const end = pay.length - size + dep;
                for (idx[dep] = dep && idx[dep-1] + 1; idx[dep] <= end; ++idx[dep])
                    if (find(sum + pay[idx[dep]], dep + 1))
                        return true;
            }
            else if (pay[idx[dep] = _.sortedLastIndex(pay, -sum) - 1] === -sum) {
                let group = _([name, pay].map(arr => _.pullAt(arr, idx)))
                    .unzip()
                    .sortBy(1)
                    .value();
                for (let left = 0, right = group.length - 1; left < right;) {
                    const money = Math.min(-group[left][1], group[right][1]);
                    result.push({
                        payer: group[left][0],
                        payee: group[right][0],
                        money
                    });
                    (group[left][1] += money) || ++left;
                    (group[right][1] -= money) || --right;
                }
                return true;
            }
            return false;
        }

        while (find(0, 0));
    }

    return result;
}

console.log(
    getPayList(list)
        .map(i => `${i.payer}支付${i.money / 100}元给${i.payee}`)
        .join('，')
);