Mengidentifikasi array dengan mean yang sama

Question

Saya menemukan masalah di mana diberikan array array integer dengan panjang berbeda [[1,2,3],[4,1,1], [9,2,1]]Anda perlu mengembalikan array array, setiap array berisi indeks dari array (dari array input) sehingga array yang sesuai memiliki rata-rata yang sama: [[0,1],[2]]Ini tampaknya relatif mudah dipecahkan menggunakan 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

Namun, ketika mencoba menyelesaikan ini di Java, ini adalah pendekatan saya: menggunakan hashmap, petakan setiap mean baru ke daftar indeks yang sesuai. Kemudian iterasi hashmap tersebut, untuk mendapatkan daftar larik dan mengubahnya menjadi larik int [] dan membuat larik 2d ...

Apakah ada pendekatan yang lebih sederhana untuk menyelesaikan masalah ini menggunakan Java?

Ini adalah kode java saya - mencari cara lain untuk menyelesaikannya:

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

Implementasi yang bagus. Beberapa saran untuk membuat metode ini groupByMeanlebih ringkas menggunakan Java Streams:

• Hitung rata-rata :

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

  Untuk:

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

• Kelompokkan menurut rata-rata :

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

  Untuk:

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

• Ubah daftar menjadi array :

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

  Untuk:

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

• Ubah nilai peta menjadi matriks :

  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;
  

  Untuk:

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

Kompleksitas Ruang / Waktu

Dalam hal kompleksitas, tidak ada perbedaan yang relevan antara solusi Anda dan solusi yang menggunakan Streams. Kompleksitas waktu masih \$O(n*m)\$dimana \$n\$adalah jumlah array dan \$m\$adalah ukuran larik terpanjang. Pada dasarnya, untuk setiap larik kita perlu menghitung rata-ratanya.

Untuk memeriksa pendekatan mana yang lebih cepat, Anda perlu membandingkan solusi.

Kode terakhir

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

Saya akan menyarankan menggunakan groupingBykolektor.

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);
}