Возвращаем общее число пар (a, b), где a из A и b - из B, a + b - <= c

Ответ 1

Мы можем решить это в O(m log m + n log m) = O(log m (m + n)) время, когда m - мощность меньшего массива; n, чем больше. Сначала отсортируйте меньший массив:

A = {32,45,9,4};
B = {43,457,54,90};

=> A = {4,9,32,45}

Теперь для каждого b в b используйте двоичный поиск в A, чтобы найти индекс наибольшего A меньше или равно (c - b). Добавьте (index + 1) к накопительному результату. Например:

c = 100:
  43  => 100 - 43  = 57   => largest a <= c-b = 45, index 3 => add 4 to result
  457 => 100 - 457 = -357 => largest a <= c-b = None
  54  => 100 - 54  = 46   => largest a <= c-b = 45, index 3 => add 4 to result
  90  => 100 - 90  = 10   => largest a <= c-b = 9,  index 1 => add 2 to result

result = 4 + 4 + 2 = 10
 corresponding with the following pairs:
 (43,4),(43,9),(43,32),(43,45),(54,4),(54,9),(54,32),(54,45),(90,4),(9,9)

Ответ 2

Давайте пощадим секунду, чтобы понять, насколько легко задача возникает при работе с Javaslang и использованием декларативного функционального подхода:

Исходные данные:

int arrayA[] = {32, 45, 9, 4};
int arrayB[] = {43, 457, 54, 90};

int c = 100;

Решение:

int result = List.ofAll(arrayA)
  .crossProduct(List.ofAll(arrayB))
  .distinct()
  .count(t -> t._1 + t._2 <= c);

Ответ 3

Если вы делаете это для практики, я рекомендую вам полностью игнорировать производительность и стремиться к ясности кода.

Часто разработчики привыкли делать свой код настолько эффективным, насколько это возможно, за счет простоты и ясности, что, как правило, плохое, так как почти невозможно заранее сказать, что будет проблемой производительности.

С точки зрения ясности, вы можете захотеть использовать Stream API вместо обычной итерации:

Arrays.stream(arrayA)
    .flatMap(n1 -> Arrays.stream(arrayB).map(n2 -> n1 + n2))
    .filter(n -> n <= total)
    .count();

Ответ 4

Начиная с сортировки массивов, это хорошая идея. Я работал бы от максимума вниз и определял, какие индексы дают значение под c:

public static int pairs(int a[], int b[], int c) {
    // a and b should be sorted before being passed here

    // Find the largest a that has a pair under c:
    int amax;
    int bmax_for_a;
    for (amax = a.length; amax > 0; amax--) {
        for (int bmax_for_a = b.length; bmax_for_a > 0; bmax_for_a--) {
            if (a[amax] + b[bmax_for_a] <= c) {
                break;
            }
        }
    }

    // Find the largest b that has a pair under c:
    int bmax;
    int amax_for_b;
    for (bmax = b.length; bmax > 0; bmax--) {
        for (int amax_for_b = a.length; amax_for_b > 0; amax_for_b--) {
            if (a[amax_for_b] + b[bmax] <= c) {
                break;
            }
        }
    }

    // Now that we have the indexes, calculate the total matches
    // and discard duplicates:
    return (amax * bmax_for_a) + (bmax * amax_for_b) - (amax_for_b * bmax_for_a);
}

Ответ 5

Мне нравится идея сортировки обоих списков и поиска краев. Тем не менее, это будет работать только в том случае, если числа в массиве имеют образец в них хорошо. (Например, {1, 2, 3' ...} или {1, 3, 5, ...}), вы можете создать конкретный алгоритм для этого конкретного шаблона.

Способ отрезать ненужный цикл, но будет сортировать оба массива и получить самое низкое число. И проверьте, в каком индексе вам больше не нужно искать пары. Например, - представьте A= {1, 5, 6, 12} и B {1, 2, 3, 4, 5, 6} и c равно 7.
- Для Array A самое низкое число 1. Это означает, что за пределами индекса 5 в массиве B нет совпадения, то есть вам нужно итерации до индекса 5.
- Для массива B самое низкое число равно 1. Помимо индекса 2 не должно быть возможных пар.

Таким образом вы можете отрезать часть обоих массивов, но вам все равно нужно проверять каждый индекс до этой точки, так как нет никакой гарантии, что все возможные пары удовлетворяют заданному условию.

Ответ 6

Как насчет использования NavigableSet для сортировки и для метода headSet:

public int countPairs(int[] a, int[] b, int c) {
    NavigableSet<Integer> aSet = IntStream.of(a).boxed().collect(Collectors.toCollection(TreeSet::new));
    NavigableSet<Integer> bSet = IntStream.of(b).boxed().collect(Collectors.toCollection(TreeSet::new));

    int total = 0;

    for (int aVal : aSet) {
        int max = c - aVal;
        Set<Integer> bVals = bSet.headSet(max, true);
        total += bVals.size();

        // Optimization to break from loop once there are no values small enough to satisfy the condition
        if (bVals.isEmpty()) {
            break;
        }
    }

    return total;
}

Это предполагает, что для a = [0, 1], b = [0, 1], c = 5 пары 0, 1 и 1, 0 являются различными парами. Он также группирует дубликаты в каждом массиве, но это может быть обработано с помощью некоторого дополнительного ведения записей (что затрудняет выполнение алгоритма).