时间戳

首页 > 解决方案 > 根据均值对数组进行排序

javascript - 根据均值对数组进行排序

问题描述

我刚刚完成了一次编码评估，并且无法通过他们的方式对数组进行排序。每个组应包含一组索引（i，j 等），以使相应的数组全部（a[i]，，a[j]等）都具有相同的均值。

例如：

let a = [[3,3,4,2],
         [4,4],
         [4,0,3,5],
         [3,3]
       ]
function sortMean(a) {
let newArr = a.sort(function (a, b) {
  let sum1 = a.reduce(function (c, d) {
    return c + d;
  });
  let sum2 = b.reduce(function (c, d) {
    return c + d;
  });

  let mean1 = sum1 / a.length;
  let mean2 = sum2 / b.length;
  return mean1 - mean2;
});

sortMean(a)
expected output: [[0,2,3],[1]]

到目前为止，我能够按他们的方式进行排序，但是在将它们分组为数组及其索引时遇到了问题。

标签： javascriptarrays

解决方案

Array#reduce是你的朋友吗？只需取每个平均值并在映射到值的键（平均值）上构建一个对象分组，这些值是与该平均值匹配的所有索引的数组。使用第三个参数来reduce获取索引。

分组后，使用Object.values砍掉键，你就剩下结果了。

const a = [
  [3,3,4,2],
  [4,4],
  [4,0,3,5],
  [3,3]
];
  
const sum = a => a.reduce((a, e) => a + e, 0);
const avg = a => sum(a) / a.length;

const result = Object.values(a.reduce((a, e, i) => {  
  const mean = avg(e);
  
  if (!a[mean]) {
    a[mean] = [];
  }
  
  a[mean].push(i);
  return a;
}, {}));

console.log(result);

另请注意，您的sort方法可能有效，但充其量是 O(n log(n)) 时间，而这应该在线性时间内可行（忽略上面提到的小数点）。此外，您在比较器中多次计算数组的平均值，这相当于很多额外的工作——最好预先进行计算。

由于平均值通常是小数，如果您需要使用 epsilon 来存储，问题就会变得更加有趣。如果这是一次采访，我会问这个问题。您可以使用舍入来分箱足够接近的浮点数，这些浮点数仍然是线性的。

推荐阅读