Как найти все пары (a, b) и (c, d) в массиве, которые удовлетворяют ab = cd с O (n²) временной сложностью, используя тип данных hashmap

Question

Учитывая список целых чисел, как все пары (то есть. Axb = cxd; такие, что a! = B! = C! = E) быть найдены при минимальной временной сложности?

Я пробовалиспользуя тип данных hashmap, который в основном выполняет вычисление продукта, проверяет, найден ли он уже внутри hashmap, и, если это так, он атрибутирует значение счетчика приращений вложенных циклов for с типом объекта Pair, найденным в hashmap.

Пара - это объект, хранящий индекс первого и второго чисел в паре.Хэш-карта хранит продукт в качестве ключа, а пару - в качестве значения.

Проблема с моим кодом заключается в том, что когда дело доходит до следующего сценария ...

axb = cxd = exf

... он не работает из-за того, что он создает только следующие ссылки ...

axb = cxd и axb = exf

... и являетсяневозможно достичь:

cxd = exf

Например, следующий массив дает неверные результаты:

int[] A = {1,2,3,4,6,12};

Я ожидаю, что единственная проблема заключается в том, что хэш-карта принимает только одно значениедля данного ключа.Возможно, я пытался изменить объявление hashmap на массив пар, но быстро понял, что мне понадобится добавить еще один цикл for, что увеличит сложность времени.

Любые идеи, которые я могу сделать, чтобы сохранитьO (n²) и предоставить правильные результаты?

Answer 1

Мое мнение:

Храните набор пар для каждого товара. Это должно заботиться о дубликатах. Вы должны считать пары равными, если они состоят из одинаковых чисел.

import java.util.HashMap;
import java.util.HashSet;
import java.util.Objects;

public class Main {

  static int[] data = {1,2,3,4,6,12};

  static class Pair {

    public Pair(int x, int y) {
      this.x = x;
      this.y = y;
    }

    public int x;
    public int y;

    @Override
    public boolean equals(Object o) {
      if (this == o) return true;
      if (o == null || getClass() != o.getClass()) return false;
      Pair pair = (Pair) o;
      return
        x == pair.x && y == pair.y ||
        x == pair.y && y == pair.x;
    }

    @Override
    public int hashCode() {
      return Objects.hash(x * y);
    }
  }

  public static void main(String[] args){

    HashMap<Integer, HashSet<Pair>> products = new HashMap<>();

    // index all pairs by product in o^2 loop
    for (int i=0;i<data.length;i++){
      for (int j=i+1;j<data.length;j++){
        int a = data[i];
        int b = data[j];
        Integer p = a*b;
        if (!products.containsKey(p)){
          products.put(p, new HashSet<>());
        }
        HashSet<Pair> knownPairs = products.get(p);
        Pair pair = new Pair(a, b);
        knownPairs.add(pair);
      }
    }

    // output results
    for (Integer product: products.keySet()) {
      System.out.print("product: "+product+" -");
      HashSet<Pair> pairs = products.get(product);
      for (Pair pair : pairs) {
        System.out.print(" "+pair.x+"x"+pair.y);
      }
      System.out.println();
    }


  }

}