Определить, существует ли A + B = C в массиве из n целых чисел - PullRequest
Новая
       0

Определить, существует ли A + B = C в массиве из n целых чисел

16 голосов
/ 30 января 2011

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

В диапазоне [0, 2 * * случайных целых числа31 -1] (могут быть дубликаты. Определите, удовлетворяют ли 3 числа из этих чисел A + B = C .

Сначала я придумал наивный алгоритм O ( n 2 log n ). Затем я придумал алгоритм O ( n 2 ). Вот псевдокод: 

sort(a); // non-descending
for (i = 0; i < n; i++) {
  j = i; k = i + 1;
  while (j < n && k < n) {
    if (a[i] + a[j] == a[k])
      return true;
    else if (a[i] + a[k] < a[j])
      k++;
    else
      j++;
  }
}
return false;

Однако проблема гласит, что 1 <<em> n <= 10 <sup>6 . Я считаю, что O ( n 2 ) слишком медленный. Мое решение не использует случайность. Однако я не уверен, является ли это важной частьюпроблемы.

Ответы [ 5 ]

13 голосов
/ 30 января 2011

Общая проблема: 3SUM-Hard , и вопрос о том, существует ли алгоритм лучше, чем квадратичный, открыт.

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

3 голосов
/ 30 января 2011

Если числа случайные, любой алгоритм O(n^2) в худшем случае (включая ваш) будет работать очень быстро. Фактически, практическая сложность будет O(n*logn) (сложность сортировки).
Это очень похоже на быструю сортировку, где у нас среднее значение O(n*logn) и небольшой шанс попасть на O(n^2).

10^6 случайные числа дают нам ~ 10^6*10^6 'почти случайные' суммы в диапазоне ~ 0..10^9. Какова вероятность того, что одна из этих 10^12 случайных сумм будет равна заданному случайному значению в целочисленном диапазоне? Довольно хорошо.
Теперь, какова вероятность того, что одна из этих 10^12 случайных сумм будет равна одной из 10 ^ 6 заданных случайных значений? 100%, говоря поэтично.

Я реализовал предложенное вами решение, для n = 10^6 он выполняет в среднем 5000-10000 операций в самом внутреннем цикле. Так много для O(n^2). Сортировка - самая дорогая операция там.

PS. Вы можете уменьшить сложность дальше и сделать ее даже O(1), если вы обновите решение, чтобы использовать хэш вместо сортировки.

PS 2. Тестовая программа на Java, для справки. Запустите его и убедитесь сами. 

    int n = 1000000;
    int[] a = new int[n];

    // generate random array
    Random r = new Random();
    for (int i = 0; i < n; ++i) {
        do {
            a[i] = r.nextInt();
        } while (a[i] < 0);
    }

    Arrays.sort(a);

    // number of operations inside main loop
    int ops = 0;

    // main logic, pretty much as OP described it
    boolean found = false;
    for (int i = 0; i < n && !found; ++i) {
        int j = i;
        int k = i + 1;
        while (k < n) {
            ++ops;

            if (a[i] > a[k] - a[j]) {
                ++k;
            } else if (a[i] < a[k] - a[j]) {
                ++j;
            } else {
                System.out.println(a[i] + " + " + a[j] + " = " + a[k]);
                found = true;
                break;
            }
        }
    }

    System.out.println(ops);
2 голосов
/ 30 января 2011

Алгоритм, который использует хеширование, занимает 10-900 микросекунд в Python (среднее значение: 200, медиана: 60): 

#!/usr/bin/env python
import random

L = frozenset(random.sample(xrange(2**31), 10**6))
print next(((a,b,a+b) for a in L for b in L if (a + b) in L), None)

Это O(N**2), но, кажется, это достаточно быстро.

Для сравнения амортизированная O(N) операция создания frozenset занимает 270 миллисекунд (в 1000 раз медленнее, чем поиск), а для создания случайного списка требуется 0.9 секунд .

Примечание: random.sample не возвращает повторяющиеся элементы, если входная последовательность содержит уникальные элементы, поэтому frozenset не удаляет какие-либо элементы в приведенном выше примере. Чтобы решить проблему для случайной последовательности, которая допускает повторяющиеся элементы, мы должны использовать две структуры данных: 

#!/usr/bin/env python
import random

L = [random.randrange(2**31) for _ in xrange(10**6)]
S = frozenset(L)
print len(L), len(S)
print next(((a, b, a+b) for a in L for b in L if (a + b) in S), None)

выход 

1000000 999762
(2055933464, 83277289, 2139210753)
1 голос
/ 31 января 2011

Я получаю O (n log n) при измерении этого по отсортированным спискам: 

from bisect import bisect_right
import cProfile as prof
import random

def find3sum(T):
    if len(T) < 3:
        return None
    n = len(T)
    top = T[-1]
    for i in range(len(T)-1):
        b = top - T[i]
        if b < T[i]:
            return None
        k = bisect_right(T, b, i, n-1)
        while k > i:
            c = T[i] + T[k]
            j = bisect_right(T, c, k, n-1)
            if j <= k:
                break
            elif T[j] == c:
               return (i, k, j)
            else:
               k -= 1

def test_one(a):
    a = sorted(a)
    r = find3sum(a)
    i, k , j = r
    assert a[i] + a[k] == a[j]

def test():
    n = 100000
    max = 200000
    random.seed(0)
    for _ in range(100):
        a = [random.randint(0,max) for _x in xrange(n)]
        test_one(a)
        a = range(n)
        test_one(a)

prof.run('test()')

Это результаты (примерно один вызов деления на элемент): 

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.002    0.002  183.764  183.764 <string>:1(<module>)
      200    0.005    0.000   89.996    0.450 find2sum.py:25(test_one)
        1   17.269   17.269  183.762  183.762 find2sum.py:31(test)
      200   35.096    0.175   79.601    0.398 find2sum.py:5(find3sum)
 10000000   44.958    0.000   52.398    0.000 random.py:160(randrange)
 10000000   23.891    0.000   76.289    0.000 random.py:224(randint)
        1    0.000    0.000    0.000    0.000 random.py:99(seed)
 19599982   44.077    0.000   44.077    0.000 {_bisect.bisect_right}
        1    0.000    0.000    0.000    0.000 {function seed at 0x9a1972c}
      600    0.001    0.000    0.001    0.000 {len}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
 10000000    7.440    0.000    7.440    0.000 {method 'random' of '_random.Random' objects}
      301    0.635    0.002    0.635    0.002 {range}
      200   10.390    0.052   10.390    0.052 {sorted}

Существует несколько оптимизаций, которые могут значительно сократить время работы (например, пропуск чисел, равных уже протестированному).

0 голосов
/ 30 января 2011

A + B = C, следовательно, B = CA или A = CB

Приведенная выше проблема может быть решена в O (n) сложности с использованием хеш-таблицы.это помогает.

...