根据平均值对数组的数组进行排序

Question

我刚完成了一项编程评估，对于按其平均值排序的数组组成的数组，我遇到了麻烦。每个组应包含一组索引（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]]

到目前为止，我能够按他们的均值进行排序，但在将它们分组成数组和它们的索引方面遇到了问题。

- pythonNovice

---

预期输出不应该是 [3,3,3,4] 吗？ - Faraz

所以这些是我排序的方式，但预期的输出应该包含具有相同平均值的索引数组的数组。 - pythonNovice

Answer 1

Array#reduce 是个好帮手。只需遍历每个平均值，构建一个对象分组，将 key(平均值) 映射到值为匹配该平均值的所有索引数组。使用 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);

注意你的排序方式可能有效，但最好情况下需要 O(n log(n)) 时间，而这应该可以在线性时间内完成（不考虑上面提到的小数问题）。另外，你在比较器中多次计算数组的平均值，这会带来很多额外的工作量，最好在前面进行这个计算。

由于平均数通常是小数，如果你需要使用 epsilon 进行分桶，这个问题就变得更有趣了。如果这是一次面试，我会问一下这个问题。你可以使用四舍五入将接近的浮点数划分到相同的区间内，这仍然是线性的。

- ggorlen

---

谢谢！只是想澄清一下（因为我对reducer函数的了解很少），在Object.values之后reducer中的累加器参数是初始数组，对吗？我对这部分有点困惑。 - pythonNovice

正确。请查看文档链接以获取有关reduce的更多上下文和示例。 - ggorlen

Answer 2

我正在使用Python完成同样的挑战：

def meangroup(a):
    mean_list = []
    group_mean = []
    for idx,i in enumerate(a):
        mean_value = sum(i)/len(i)
        if mean_value in mean_list:
            group_mean[mean_list.index(mean_value)].append(idx)
        else:
            group_mean.append([idx])
        mean_list.append(mean_value)
    return  group_mean

- MatChen

Answer 3

我在Python中是这样做的，对我来说最有意义。

def solution(a):
    means={}
    for i in range(len(a)):
        avg = sum(a[i]) / len(a[i])
        averages_lst = means.get(avg, [])
        averages_lst.append(i)
        means[avg] = averages_lst 
    answer=list(means.values())
    return answer

- Cole Meier

Answer 4

我喜欢 Kotlin <3

fun main() {
    val arr = arrayOf(arrayOf(3, 3, 4, 2), arrayOf(4, 4), arrayOf(4, 0, 3, 5), arrayOf(3, 3))

    val map = mutableMapOf<Int, MutableList<Int>>()

    for ((i, mArray) in arr.withIndex()) {
        val mean = mArray.average().toInt()
        val meanList: MutableList<Int> = map[mean] ?: mutableListOf()
        meanList.add(i)
        map[mean] = meanList
    }

    println(map.values.toList())
}

- Rodrigo Salomao

Answer 5

我觉得这个挑战很有趣，所以我尝试了一下。我用Java写的，但它可以很容易地转换成你想要的任何语言。

int[][] arr = { { 3, 3, 4, 2 }, { 4, 4 }, { 4, 0, 3, 5 }, { 3, 3 } };

Map<Integer, List<Integer>> map = new TreeMap<>();

for (int i = 0; i < arr.length; i++) {
    int mean = mean(arr[i]);
    if (map.containsKey(mean)) {
        List<Integer> l = map.get(mean);
        l.add(i);
        map.put(mean, l);
    } else {
        List<Integer> l = new ArrayList<>();
        l.add(i);
        map.put(mean, l);
    }
}

选择TreeMap，因为它会按升序（排序）保留键。这个Map将以均值为键，以一个列表中的指数为值。然后我们遍历数组，找到均值，将其添加到映射和列表中的索引，并且如果映射已经包含该均值，则将索引添加到现有列表中。

int finArr[][] = new int[map.values().size()][]; //this will hold the final answer--arrays of indices. 

List<Integer> keys = new ArrayList<>(map.keySet());

map.keySet() 会按升序返回键（因为我们选择创建了一个 TreeMap 类型的 Map），但我们想立即将其转换为 ArrayList，因为我们无法使用索引从 Set 中提取值。而且我们还需要索引将数组正确地放入最终数组的正确位置。

for (int i = 0; i < keys.size(); i++) {
    finArr[i] = map.remove(keys.get(i)).stream().mapToInt(val -> val).toArray();
}

在上面的for循环中，我们基本上是从映射中提取值（即列表），并将该列表转换为原始int数组。

System.out.print("[ ");
for (int[] is : finArr) {
    System.out.print(Arrays.toString(is) + " ");
}
System.out.println("]");

输出：[ [0, 2, 3], [1] ]

平均方法：

private static int mean(int[] arr) {
    int sum = 0;
    for (int i : arr) {
        sum += i;
    }
    return sum / arr.length;
}

奖励::

这个变种的插入排序可以根据平均值对数组进行排序。

for (int i = 1; i < arr.length; i++) {
    int[] kk = arr[i];
    int key = mean(arr[i]);
    int j = i - 1;
    while (j > -1 && mean(arr[j]) > key) {
        arr[j + 1] = arr[j];
        j--;
    }
    arr[j + 1] = kk;
}

for (int[] is : arr) {
    System.out.println(Arrays.toString(is));
}

输出：[3,3,3,4]

- Faraz