Identificar matrices con la misma media

Question

Me encontré con un problema en el que, dada una matriz de matrices enteras de diferentes longitudes [[1,2,3],[4,1,1], [9,2,1]], necesita devolver una matriz de matrices, cada matriz contiene índices de las matrices (de la matriz de entrada) de modo que las matrices correspondientes tienen la misma media: [[0,1],[2]]esto parece relativamente simple de resolver usando Python:

def groupByMean(a):
    d,e=[],[]
    for i,j in enumerate(a):
        if sum(j)/len(j)not in e:
            e+=[sum(j)/len(j)]
            d+=[[i]]
        else:
            d[e.index(sum(j)/len(j))]+=[i]
    return d

Sin embargo, cuando intenté resolver esto en Java, este fue mi enfoque: usando un mapa de hash, mapee cada nueva media a una lista de los índices correspondientes. Luego, itere el mapa hash, para obtener las listas de matrices y convertirlas en matrices int [] y construir la matriz 2d ...

¿Existe un enfoque más simple para resolver esto usando Java?

Este es mi código Java, buscando una forma diferente de resolver esto:

public static void main(String[] args) {
    int[][] arr = { { 1, 2, 3 }, { 2, 3, 4 }, { 2, 4, 0 } };
    for (int[] nums : groupBySum(arr)) {
        for (int n : nums) {
            System.out.print(n + " ");
        }
        System.out.println();
    }
}

public static int[][] groupByMean(int[][] arr) {
    Map<Double, List<Integer>> map = new HashMap<>();
    int i = 0;
    for (int[] nums : arr) {
        double average = getAverage(nums);
        if (!map.containsKey(average)) {
            List<Integer> indices = new ArrayList<>();
            indices.add(i);
            map.put(average, indices);
        } else {
            map.get(average).add(i);
        }
        i++;
    }
    int[][] result = new int[map.size()][];
    int row = 0;
    for (List<Integer> indices : map.values()) {
        result[row] = new int[indices.size()];
        for (int k = 0; k < indices.size(); k++) {
            result[row][k] = indices.get(k);
        }
        row++;
    }
    return result;
}

public static double getAverage(int[] arr) {
    int sum = 0;
    for (int num : arr) {
        sum += num;
    }
    return ((double) sum) / arr.length;
}

Answer 1

Buena implementación. Algunas sugerencias para hacer que el método sea groupByMeanmás compacto usando Java Streams:

• Calcule el promedio :

  public static double getAverage(int[] arr) {
    int sum = 0;
    for (int num : arr) {
        sum += num;
    }
    return ((double) sum) / arr.length;
  }
  

  A:

  public static double getAverage(int[] arr) {
    return Arrays.stream(nums).average().getAsDouble();
  }
  

• Agrupar por media :

  if (!map.containsKey(average)) {
      List<Integer> indices = new ArrayList<>();
      indices.add(i);
      map.put(average, indices);
  } else {
      map.get(average).add(i);
  }
  

  A:

  map.computeIfAbsent(average, v -> new ArrayList<>()).add(i);
  

• Convertir lista en matriz :

  for (int k = 0; k < indices.size(); k++) {
      result[row][k] = indices.get(k);
  }
  

  A:

  result[row] = indices.stream().mapToInt(index->index).toArray();
  

• Convierta los valores del mapa en una matriz :

  int[][] result = new int[map.size()][];
  int row = 0;
  for (List<Integer> indices : map.values()) {
      result[row] = new int[indices.size()];
      for (int k = 0; k < indices.size(); k++) {
          result[row][k] = indices.get(k);
      }
      row++;
  }
  return result;
  

  A:

  return map.values().stream()
            .map(v -> v.stream().mapToInt(index->index).toArray())
            .toArray(int[][]::new);
  

Complejidad de tiempo / espacio

En términos de complejidad, no existen diferencias relevantes entre su solución y la que usa Streams. La complejidad del tiempo sigue siendo \$O(n*m)\$donde \$n\$es el número de matrices y \$m\$es el tamaño de la matriz más larga. Básicamente, para cada matriz necesitamos calcular el promedio.

Para comprobar qué enfoque es más rápido, debe comparar las soluciones.

Código final

public static void main(String[] args) {
    int[][] arr = {{ 1, 2, 3 }, { 2, 3, 4 }, { 2, 4, 0 }};
    Arrays.stream(groupByMean(arr)).map(Arrays::toString)
        .forEach(System.out::println);
}

public static int[][] groupByMean(int[][] arr) {
    Map<Double, List<Integer>> map = new HashMap<>();
    for (int i=0 ; i<arr.length; i++) {
        double average = Arrays.stream(arr[i]).average().getAsDouble();
        map.computeIfAbsent(average, v -> new ArrayList<>()).add(i);
    }
    return map.values().stream()
      .map(v -> v.stream().mapToInt(index->index).toArray())
      .toArray(int[][]::new);
}

Answer 2

Sugeriría usar el groupingBycoleccionista.

public static void main(String[] args) {
    int[][] arr = {{ 1, 2, 3 }, { 2, 3, 4 }, { 2, 4, 0 }};
    IntStream.range(0, arr.length)
        .boxed()
        .collect(groupingBy(i->Arrays.stream(arr[i]).average().getAsDouble()))
        .values()
        .forEach(System.out::println);
}