Как найти пифагорейские тройки в массиве быстрее, чем O (N ^ 2)?

Question

Может ли кто-нибудь предложить алгоритм, который находит все пифагорейские триплеты среди чисел в данном массиве? Если возможно, предложите алгоритм быстрее, чем O (n ² ).

Пифагорейский триплет представляет собой набор {a, b, c} такой, что a ² = b ² + c ² Пример: для массива [9, 2, 3, 4, 8, 5, 6, 10] вывод алгоритма должен быть {3, 4, 5} и {6, 8, 10}.

Answer 1

Я понимаю этот вопрос как

Для данного массива найдите все такие триплеты i, j и k, чтобы a [i] ² = a [j] ² + a [к] ²

Ключевая идея решения:

• Квадрат каждого элемента . (Это занимает O (N) время). Это уменьшит исходную задачу до «поиска трех чисел в массиве, одно из которых является суммой двух других».

Теперь, если вы знаете, как решить такую ​​задачу менее чем за O (n ² ) времени, используйте такой алгоритм. Из моего разума исходит только следующее решение O (n ² ):

1. Сортировка массива в порядке возрастания. Требуется O (n log n).

2. Теперь рассмотрим каждый элемент a [i]. Если a [i] = a [j] + a [k], то, поскольку числа положительны и массив теперь отсортирован, k Чтобы найти такие индексы, запустите цикл, который увеличивает j с 1 до i и уменьшает k с i до 0 одновременно, пока они не встретятся. Увеличьте j, если a[j]+a[k] < a[i], и уменьшите k, если сумма больше a[i]. Если сумма равна, это один из ответов, распечатайте его и сдвиньте оба индекса.

   Требуется O (i) операций.

3. Повторите шаг 2 для каждого индекса i. Таким образом, вам понадобится всего O (n ² ) операций, которые будут окончательной оценкой.

Answer 2

Никто не знает, как сделать значительно лучше, чем квадратичные, для тесно связанной задачи 3SUM (http://en.wikipedia.org/wiki/3SUM). Я бы оценил вероятность быстрого решения вашей проблемы как маловероятную.

---

Задача 3SUM - найти a + b + c = 0. Пусть PYTHTRIP - это проблема нахождения ^ 2 + b ^ 2 = c ^ 2, когда входные данные являются действительными алгебраическими числами. Вот сокращение времени O (n log n) с 3SUM до PYTHTRIP. Как указывает ShreevatsaR, это не исключает возможности теоретико-числового уловки (или решения 3SUM!).

Сначала мы уменьшим 3SUM до проблемы, которую я назову 3SUM-ALT. В 3SUM-ALT мы хотим найти a + b = c, где все записи массива неотрицательны. Окончательное сокращение от 3SUM-ALT до PYTHTRIP просто берет квадратные корни.

Чтобы решить 3SUM с помощью 3SUM-ALT, сначала исключите возможность тройки, где один из a, b, c равен нулю (O (n log n)). Теперь любая удовлетворяющая тройка имеет два положительных числа и одно отрицательное или два отрицательных и одно положительное. Пусть w будет числом, в три раза превышающим абсолютное значение любого входного числа. Решите два случая 3SUM-ALT: один, где все отрицательные x отображаются на w - x, а все положительные x отображаются на 2w + x; один, где все отрицательные x отображаются на 2w - x, а все положительные x отображаются на w + x. Остальная часть доказательства проста.

Answer 3

У меня есть еще одно решение,

//sort the array in ascending order 
//find the square of each element in the array

//let 'a' be the array containing square of each element in ascending order 

for(i->0 to (a.length-1))
  for (j->i+1 to  (a.length-1))
    //search the a[i]+a[j] ahead in the array from j+1 to the end of array
      //if found get the triplet according to sqrt(a[i]),sqrt(a[j]) & sqrt(a[i]+a[j])
  endfor
endfor

Answer 4

Вот решение, которое может лучше масштабироваться для больших списков небольших чисел. По крайней мере, это другое; v).

Согласно http://en.wikipedia.org/wiki/Pythagorean_triple#Generating_a_triple,

a = m^2 - n^2, b = 2mn, c = m^2 + n^2 

b выглядит хорошо, а?

• Сортировка массива по времени O (N log N).
• Для каждого элемента b найдите простую факторизацию. Наивное использование таблицы простых чисел вплоть до квадратного корня из наибольшего входного значения M займет O (sqrt M / log M) время и пространство * на элемент.
• Для каждой пары (m,n), m > n, b = 2mn (пропустите нечетное b), найдите m^2-n^2 и m^2+n^2 в отсортированном массиве. O (log N) на пару, O (2 ^ (Ω (M))) = O (log M) ** пар на элемент, всего O (N (log N) (log M)) .

Окончательный анализ: O (N ((кв. M / log M) + (log N * log M))), N = размер массива, M = величина значений.

(* Чтобы принять 64-битный ввод, существует около 203M 32-битных простых чисел, но мы можем использовать таблицу различий в один байт на простое число, поскольку все различия четные и, возможно, также генерировать большие простые числа в последовательности по требованию. Чтобы принять 32-битный ввод, необходима таблица из 16-битных простых чисел, которая достаточно мала, чтобы поместиться в кэш L1. Время здесь является завышенным, если предположить, что все простые множители чуть меньше квадратный корень.)

(** Фактическая граница ниже из-за повторяющихся простых факторов.)

Answer 5

Не уверен, что это лучше, но вы можете вычислить их во времени, пропорциональном максимальному значению в списке, просто вычислив все возможные тройки, меньшие или равные ему. Следующий код Perl делает. Временная сложность алгоритма пропорциональна максимальному значению, поскольку сумма обратных квадратов 1 + 1/2 ^ 2 + 1/3 ^ 3 .... равна Pi ^ 2/6, константе.

Я только что использовал формулу со страницы Wikipedia для генерации уникальных троек.

my $list = [9, 2, 3, 4, 8, 5, 6, 10];
pythagoreanTriplets ($list);

sub pythagoreanTriplets
{
  my $list = $_[0];
  my %hash;
  my $max = 0;
  foreach my $value (@$list)
  {
    $hash{$value} = 1;
    $max = $value if ($value > $max);
  }
  my $sqrtMax = 1 + int sqrt $max;

  for (my $n = 1; $n <= $sqrtMax; $n++)
  {
    my $n2 = $n * $n;
    for (my $m = $n + 1; $m <= $sqrtMax; $m++)
    {
      my $m2 = $m * $m;
      my $maxK = 1 + int ($max / ($m2 + $n2));
      for (my $k = 1; $k <= $maxK; $k++)
      {
        my $a = $k * ($m2 - $n2);
        my $b = $k * (2 * $m * $n);
        my $c = $k * ($m2 + $n2);
        print "$a $b $c\n" if (exists ($hash{$a}) && exists ($hash{$b}) && exists ($hash{$c}));
      }
    }
  }
}

Answer 6

Раствор в O (N).

1. узнать минимальный элемент в массиве. мин O (n).
2. узнать максимальный элемент в массиве. max O (n).
3. создает таблицу элементов, чтобы можно было искать элемент в O (1).
4. m ^ 2-1 = min .... введите min из шага 1. найдите m в этом уравнении. O (1)
5. 2m = min .... введите min из шага 1. найдите m в этом уравнении. O (1)

6. m ^ 2 + 1 = max .... введите max из шага 2. найдите m в этом уравнении. O (1)

7. выберите минимальный этаж (шаги 4,5,6), скажем, minValue.O (1)

8. выберите максимальный уровень (шаги 4,5,6), скажем, maxValue.O (1)

9. цикл от j = minValue до maxValue. maxvalue-minvalue будет меньше, чем корень N. 9.a вычислить три числа j ^ 2-1,2j, j ^ 2 + 1. 9.b искать эти числа в хеш-таблице. если найден, верните успех.

10. ошибка возврата.

Answer 7

Некоторым моим сотрудникам была задана эта та же проблема в курсе java-сертификации, в котором они брали решение, которое мы придумали, было O (N ^ 2). Мы сократили как можно больше проблемного пространства, но не смогли найти способ снизить сложность до N Log N или лучше.

    public static List<int[]> pythagoreanTripplets(int[] input) {
    List<int[]> answers = new ArrayList<int[]>();
    Map<Long, Integer> map = new HashMap<Long, Integer>();

    for (int i = 0; i < input.length; i++) {
        map.put((long)input[i] * (long)input[i], input[i]);
    }

    Long[] unique = (Long[]) map.keySet().toArray(new Long[0]);
    Arrays.sort(unique);
    long comps =0;
    for(int i =  1 ; i < unique.length;i++)
    {
        Long halfC = unique[i]/2;
        for(int j = i-1 ; j>= 0 ; j--)
        {

            if(unique[j] < halfC) break;
            if(map.containsKey(unique[i] - unique[j]))
            {
                answers.add(new int[]{map.get(unique[i] - unique[j]),map.get(unique[j]),map.get(unique[i])});
            }
        }
    }
    return answers;
}

Answer 8

Это можно сделать за O (n) раз. сначала хэшируйте элементы в карте для проверки существования. после этого примените приведенный ниже алгоритм

Сканирование массива, и если элемент является четным числом, (n, n ^ 2/2 +1, n ^ 2/2 -1) можно найти триплет просто проверьте наличие, используя поиск по хэш-карте. если все элементы в триплете существуют, выведите триплет.

Answer 9

Это тот, который я реализовал ...

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;


/**
 * 
 * @author Pranali Choudhari (pranali_choudhari@persistent.co.in)
 */
public class PythagoreanTriple {

/
    //I hope this is optimized



    public static void main(String[] args) {

        Map<Long,Set<Long>> triples = new HashMap<Long,Set<Long>>();
        List<Long> l1 = new ArrayList<Long>();
        addValuesToArrayList(l1);
        long n =0;        
        for(long i : l1){
            //if its side a.
             n = (i-1L)/2L;
             if (n!=0 && n > 0){
                  putInMap(triples,n,i);
                  n=0;
             }
             //if its side b 

             n = ((-1 + Math.round(Math.sqrt(2*i+1)))/2);
             if (n != 0 && n > 0){
                 putInMap(triples,n,i);
                  n=0;
             }
             n=  ((-1 - Math.round(Math.sqrt(2*i+1)))/2);
             if (n != 0 && n > 0){
                 putInMap(triples,n,i);
                  n=0;
             }
             //if its side c

             n = ((-1 + Math.round(Math.sqrt(2*i-1)))/2);
             if (n != 0 && n > 0){
                 putInMap(triples,n,i);
                  n=0;
             }
             n=  ((-1 - Math.round(Math.sqrt(2*i-1)))/2);
             if (n != 0 && n > 0){
                 putInMap(triples,n,i);
                  n=0;
             }


        }
        for(Map.Entry<Long, Set<Long>> e : triples.entrySet()){
            if(e.getValue().size() == 3){
                System.out.println("Tripples" + e.getValue());
            }
            //need to handle scenario when size() > 3 
            //even those are tripples but we need to filter the wrong ones
        }


    }

    private static void putInMap( Map<Long,Set<Long>> triples, long n,  Long i) {
        Set<Long> set = triples.get(n);
        if(set == null){
            set = new HashSet<Long>();
            triples.put(n, set);
        }
        set.add(i);
    }

    //add values here 
    private static void addValuesToArrayList(List<Long> l1) {
        l1.add(1L);
        l1.add(2L);
        l1.add(3L);
        l1.add(4L);
        l1.add(5L);
        l1.add(12L);
        l1.add(13L);

    }
}

Answer 10

Если (a, b, c) - пифагорейская тройка, то и (ka, kb, kc) - для любого натурального числа

, так что просто найдите одно значение для a, b и c, и тогда вы сможете вычислить столько новых значений, сколько захотите.

Псевдокод:

a = 3
b = 4
c = 5
for k in 1..N:
  P[k] = (ka, kb, kc)

Дайте мне знать, если это не совсем то, что вы ищете.