Как найти все упорядоченные пары элементов в массиве целых чисел, сумма которых лежит в заданном диапазоне значений

Ответ 1

• Сортировка массива (скажем, в порядке возрастания).
• Для каждого элемента x в массиве:
  • Рассмотрим срез массива после элемента.
  • Сделайте двоичный поиск на этом массиве для [a-x], назовите его y0. Если точное совпадение не найдено, рассмотрите ближайшее совпадение больше, чем [a-x] как y0.
  • Вывести все элементы (x, y) из y0 вперед до тех пор, пока x + y <= b

Временная сложность, конечно, чувствительна к выходным характеристикам, но она по-прежнему превосходит существующий алгоритм:

O(nlogn) + O(k)

где k - число пар, удовлетворяющих условию.

Примечание. Если вам нужно только подсчитать количество пар, вы можете сделать это в O(nlogn). Измените вышеописанный алгоритм, так что [b - x] (или следующий меньший элемент) также выполняется поиск. Таким образом, вы можете подсчитать количество совпадений каждого элемента в O(logn) просто из индексов первого и последнего совпадений. Тогда это просто вопрос подведения итогов, чтобы получить окончательный счет. Таким образом, начальный шаг сортировки O(nlogn) является доминирующим.

Ответ 2

Сначала отсортируйте массив и подсчитайте пары двумя индексами. Подход двух индексов аналогичен подходу 2-sum problem, который позволяет избежать двоичного поиска N раз. Время, затрачиваемое на алгоритм, составляет Sort Complexity + O(N), как правило, sort - это O (NlnN), поэтому этот подход O (NlnN). Идея алгоритма заключается в том, что для индекса i найти нижнюю грань и верхнюю границу, такую, что a <= arr[i]+arr[low] <= arr[i]+arr[high] <= b и когда i увеличивается, нам нужно уменьшить low и high состояние. Чтобы не считать одну и ту же пару дважды, мы сохраняем low > i, также сохраняем low <= high. Сложность следующего подхода подсчета - O (N), потому что в while loop мы можем сделать это ++i или --low или --high и не более N таких операций.

//count pair whose sum is in [a, b]
//arr is a sorted array with size integers.
int countPair(int arr[], int size, int a, int b) {
    int cnt = 0;
    int i = 0, low = size-1, high = size－1;
    while (i < high) {
        //find the lower bound such that arr[i] + arr[low] < a, 
        //meanwhile arr[i]+arr[low+1] >= a
         low = max(i, low);
         while (low > i && arr[i] + arr[low] >= a) --low;

        //find an upper bound such that arr[i] + arr[high] <= b 
        //meanwhile, arr[i]+arr[high+1] > b
        while (high > low && arr[i] + arr[high] > b) --high; 
        //all pairs: arr[i]+arr[low+1], arr[i]+arr[low+2],...,arr[i]+arr[high]
        //are in the rage[a, b], and we count it as follows.
        cnt += (high-low);
        ++i;
    }
    return cnt;
}

Ответ 3

Проблема подсчета пар, которые работают, может быть выполнена во время сортировки + O (N). Это быстрее, чем решение, которое дает Ani, которое является временем сортировки + O (N log N). Идея такая. Сначала вы сортируете. Затем вы выполняете почти один и тот же алгоритм с одним проходом. Затем вы можете использовать результаты двух алгоритмов с одним проходом для вычисления ответа.

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

a = 6
array = [-20, 1, 3, 4, 8, 11]
output = [6, 4, 2, 2, 1, 1]

Итак, число в индексе массива 1 равно 1 (индексирование на основе 0). Наименьшее число, с которым он может соединиться, чтобы получить более 6, - это восьмерка, которая находится в индексе 4. Следовательно, выход [1] = 4. -20 не может соединяться ни с чем, поэтому выход [0] = 6 (за пределами), Другой пример: output [4] = 1, потому что 8 (индекс 4) может спариваться с 1 (индекс 1) или любым числом после него суммировать более 6.

Теперь вам нужно убедить себя, что это O (N). Это. Код:

i, j = 0, 5
while i - j <= 0:
  if array[i] + array[j] >= a:
    output[j] = i
    j -= 1
  else:
    output[i] = j + 1
    i += 1

Просто подумайте о двух указателях, начинающихся с краев и работающих вовнутрь. Это на). Теперь вы делаете то же самое, только с условием b <= a:

while i-j <= 0:
  if array[i] + array[j] <= b:
    output2[i] = j
    i += 1
  else:
    output2[j] = i-1
    j-=1

В нашем примере этот код дает вам (массив и b для справки):

b = 9
array = [-20, 1, 3, 4, 8, 11]
output2 = [5, 4, 3, 3, 1, 0]

Но теперь вывод и вывод2 содержат всю необходимую нам информацию, поскольку они содержат диапазон действительных индексов для спариваний. output - наименьший индекс, с которым он может быть сопряжен, output2 - это самый большой индекс, с которым он может быть сопряжен. Разница + 1 - количество спариваний для этого местоположения. Таким образом, для первого местоположения (соответствующего -20) существует 5 - 6 + 1 = 0 спариваний. Для 1 существует 4-4 + 1 спаривания, число с индексом 4, равное 8. Еще одна тонкость, этот алгоритм учитывает самоспасания, поэтому, если вы этого не хотите, вы должны вычесть. Например. 3, по-видимому, содержит 3-2 + 1 = 2 пары, один по индексу 2 и один по индексу 3. Конечно, сам по себе 3 находится в индексе 2, поэтому один из них является спариванием, а другой - спариванием с 4. Вам просто нужно вычитать его каждый раз, когда диапазон индексов output и output2 содержит сам индекс, на который вы смотрите. В коде вы можете написать:

answer = [o2 - o + 1 - (o <= i <= o2) for i, (o, o2) in enumerate(zip(output, output2))]

Что дает:

answer = [0, 1, 1, 1, 1, 0]

Какие суммы равны 4, соответствующие (1,8), (3,4), (4,3), (8, 1)

Во всяком случае, как вы можете видеть, это сортировка + O (N), которая является оптимальной.

Изменить: требуется полная реализация. Предоставлена. Для справки, полный код:

def count_ranged_pairs(x, a, b):
    x.sort()

    output = [0] * len(x)
    output2 = [0] * len(x)

    i, j = 0, len(x)-1
    while i - j <= 0:
      if x[i] + x[j] >= a:
        output[j] = i
        j -= 1
      else:
        output[i] = j + 1
        i += 1

    i, j = 0, len(x) - 1
    while i-j <= 0:
      if x[i] + x[j] <= b:
        output2[i] = j
        i += 1
      else:
        output2[j] = i-1
        j -=1

    answer = [o2 - o + 1 - (o <= i <= o2) for i, (o, o2) in enumerate(zip(output, output2))]
    return sum(answer)/2

Ответ 4

from itertools import ifilter, combinations

def countpairs2(array, a, b):
    pairInRange = lambda x: sum(x) >= a and sum(x) <= b
    filtered = ifilter(pairInRange, combinations(array, 2))
    return sum([2 for x in filtered])

Я думаю, что библиотека Itertools очень удобна. Я также заметил, что вы считали пары дважды, например, вы считали (1, 3) и (3, 1) как две разные комбинации. Если вы этого не хотите, просто измените 2 в последней строке на 1. Примечание. Последнее может быть изменено на return len(list(filtered)) * 2. Это МОЖЕТ быть быстрее, но за счет использования большего объема оперативной памяти.

Ответ 5

С некоторыми ограничениями на данные мы можем решить проблему в линейном времени (извините за Java, я не очень разбираюсь в Python):

public class Program {
    public static void main(String[] args) {
        test(new int[]{-2, -1, 0, 1, 3, -3}, -1, 2);
        test(new int[]{100,200,300}, 300, 300);
        test(new int[]{100}, 1, 1000);
        test(new int[]{-1, 0, 0, 0, 1, 1, 1000}, -1, 2);
    }

    public static int countPairs(int[] input, int a, int b) {
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (int el : input) {
            max = Math.max(max, el);
            min = Math.min(min, el);
        }
        int d = max - min + 1; // "Diameter" of the array
        // Build naive hash-map of input: Map all elements to range [0; d]
        int[] lookup = new int[d];
        for (int el : input) {
            lookup[el - min]++;
        }
        // a and b also needs to be adjusted
        int a1 = a - min;
        int b1 = b - min;
        int[] counts = lookup; // Just rename
        // i-th element contain count of lookup elements in range [0; i]
        for (int i = 1; i < counts.length; ++i) {
            counts[i] += counts[i - 1];
        }
        int res = 0;
        for (int el : input) {
            int lo = a1 - el; // el2 >= lo
            int hi = b1 - el; // el2 <= hi
            lo = Math.max(lo, 0);
            hi = Math.min(hi, d - 1);
            if (lo <= hi) {
                res += counts[hi];
                if (lo > 0) {
                    res -= counts[lo - 1];
                }
            }
            // Exclude pair with same element
            if (a <= 2*el && 2*el <= b) {
                --res;
            }
        }
        // Calculated pairs are ordered, divide by 2
        return res / 2;
    }

    public static int naive(int[] ar, int a, int b) {
        int res = 0;
        for (int i = 0; i < ar.length; ++i) {
            for (int j = i + 1; j < ar.length; ++j) {
                int sum = ar[i] + ar[j];
                if (a <= sum && sum <= b) {
                    ++res;
                }
            }
        }
        return res;
    }

    private static void test(int[] input, int a, int b) {
        int naiveSol = naive(input, a, b);
        int optimizedSol = countPairs(input, a, b);
        if (naiveSol != optimizedSol) {
            System.out.println("Problem!!!");
        }
    }
}

Для каждого элемента массива мы знаем диапазон, в котором может лежать второй элемент пары. Ядром этого алгоритма является подсчет элементов в диапазоне [a; b] в течение O (1).

Результирующая сложность - O (max (N, D)), где D - разность между макс и min элементами массива. Если это значение имеет тот же порядок, что и N - сложность O (N).

Примечания:

• Нет сортировки!
• Требуется поиск здания, чтобы алгоритм работал с отрицательным чисел и сделать второй массив как можно меньшим (положительно влияет как на память, так и на время)
• Требуется худшее условие if (a <= 2*el && 2*el <= b), потому что алгоритм всегда считает пары (a [i], a [i])
• Алгоритм требует O (d) дополнительной памяти, которая может быть много.

Другим линейным алгоритмом будет подсчет счисления счисления + линейной пары.

ИЗМЕНИТЬ. Этот алгоритм может быть действительно хорош в случае, если D значительно меньше N, и вам не разрешается изменять входной массив. Альтернативным вариантом для этого случая будет слегка измененная сортировка сортировки с выделением массива counts (дополнительная O (D) память), но без заполнения отсортированных элементов обратно на входной массив. Можно настроить парный счет для использования массива counts вместо полного отсортированного массива.

Ответ 6

У меня есть решение (на самом деле 2 решения;-)). Запись в python:

def find_count(input_list, min, max):
    count = 0
    range_diff = max - min
    for i in range(len(input_list)):
        if input_list[i]*2 >= min and input_list[i]*2 <= max:
            count += 1
        for j in range(i+1, len(input_list)):
            input_sum = input_list[i] + input_list[j]
            if input_sum >= min and input_sum <= max:
                count += 2

Это приведет к выполнению nCr (n комбинаций) раз до max и даст вам необходимый счетчик. Это будет лучше, чем сортировка списка, а затем поиск пар в диапазоне. Если количество элементов, которые выходят из строя, больше, а все числа - целые положительные числа, мы можем улучшить результат немного лучше, добавив условие, которое проверяет элементы для

• Номера, которые не попадают под диапазон даже с добавлением максимального значения
• Числа, превышающие максимальное число.

Что-то вроде этого:

# list_maximum is the maximum number of the list (i.e) max(input_list), if already known
def find_count(input_list, min, max, list_maximum):
    count = 0
    range_diff = max - min
    for i in range(len(input_list)):
        if input_list[i] > max or input_list[i] + list_maximum < min:
            continue
        if input_list[i]*2 >= min and input_list[i]*2 <= max:
            count += 1
        for j in range(i+1, len(input_list)):
            input_sum = input_list[i] + input_list[j]
            if input_sum >= min and input_sum <= max:
                count += 2

Я также с удовольствием узнаю любое лучшее решение, чем это:-) Если я натолкнулся на один, я обновлю этот ответ.

Ответ 7

Я считаю, что это простая математическая проблема, которая может быть решена с помощью numpy без петель и без сортировки с нашей стороны. Я не совсем уверен, но я считаю, что сложность быть O (N ^ 2) в худшем случае (хотелось бы получить некоторое подтверждение от этого кем-то, более осведомленным о временных сложностях в numpy).

Во всяком случае, здесь мое решение:

import numpy as np

def count_pairs(input_array, min, max):
    A = np.array(input_array)
    A_ones = np.ones((len(A),len(A)))
    A_matrix = A*A_ones
    result = np.transpose(A_matrix) + A_matrix
    result = np.triu(result,0)
    np.fill_diagonal(result,0)
    count = ((result > min) & (result < max)).sum()
    return count

Теперь пройдите через него - сначала я просто создаю матрицу с столбцами, представляющими наши числа:

A = np.array(input_array)
A_ones = np.ones((len(A),len(A)))
A_matrix = A*A_ones

Предположим, что наш входной массив выглядел так: [1,1,2,2,3,-1], таким образом, это должно быть значение A_matrix в этой точке.

[[ 1.  1.  2.  2.  3. -1.]
 [ 1.  1.  2.  2.  3. -1.]
 [ 1.  1.  2.  2.  3. -1.]
 [ 1.  1.  2.  2.  3. -1.]
 [ 1.  1.  2.  2.  3. -1.]
 [ 1.  1.  2.  2.  3. -1.]]

Если я добавлю это к транспонированию себя...

result = np.transpose(A_matrix) + A_matrix

... Я должен получить матрицу, представляющую все комбинации сумм пар:

[[ 2.  2.  3.  3.  4.  0.]
 [ 2.  2.  3.  3.  4.  0.]
 [ 3.  3.  4.  4.  5.  1.]
 [ 3.  3.  4.  4.  5.  1.]
 [ 4.  4.  5.  5.  6.  2.]
 [ 0.  0.  1.  1.  2. -2.]]

Конечно, эта матрица зеркально отражается по диагонали, потому что пары (1,2) и (2,1) дают одинаковый результат. Мы не хотим рассматривать эти повторяющиеся записи. Мы также не хотим рассматривать сумму элемента с самим собой, поэтому давайте дезинфицируем наш массив:

result = np.triu(result,0)
np.fill_diagonal(result,0)

Теперь наш результат выглядит следующим образом:

[[ 0.  2.  3.  3.  4.  0.]
 [ 0.  0.  3.  3.  4.  0.]
 [ 0.  0.  0.  4.  5.  1.]
 [ 0.  0.  0.  0.  5.  1.]
 [ 0.  0.  0.  0.  0.  2.]
 [ 0.  0.  0.  0.  0.  0.]]

Осталось только подсчитать элементы, которые соответствуют нашим критериям.

count = ((result > min) & (result < max)).sum()

Предупреждение:

Этот метод не будет работать, если 0 находится в допустимом домене, но я уверен, что было бы тривиально манипулировать этой матрицей результатов выше, чтобы преобразовать эти 0 в другое бессмысленное число....

Ответ 8

Вместо использования реляционных операторов мы можем просто проверить, сумма элементов массива я и j находится в указанном диапазоне.

def get_numOfPairs(array, start, stop):
    num_of_pairs = 0
    array_length = len(array)

    for i in range(array_length):
        for j in range(i+1, array_length):
            if sum([array[i], array[j]]) in range(start, stop):
                num_of_pairs += 1

    return num_of_pairs