Как найти пифагорейские триплеты в массиве быстрее, чем O (N ^ 2)?
Может кто-нибудь предложить алгоритм, который находит все пифагорейские триплеты среди чисел в заданном массиве? Если это возможно, предложите алгоритм быстрее, чем O (n 2).
Пифагорейский триплет есть множество {a, b, c} такое, что a 2= b 2 + c 2. Пример: для массива [9, 2, 3, 4, 8, 5, 6, 10] вывод алгоритма должен быть {3, 4, 5} и {6, 8, 10}.
Ответы
Ответ 1
Я понимаю этот вопрос как
Для массива найдите все такие триплеты i, j и k, так что a [i] 2= a [j] 2 + а [к] 2
Основная идея решения:
- Квадрат каждого элемента. (Это занимает время O (n)). Это уменьшит исходную задачу, чтобы "найти три числа в массиве, одна из которых представляет собой сумму двух других".
Теперь вы знаете, как решить такую задачу за меньшее время O (n 2), используйте такой алгоритм. Из моего разума приходит только следующее решение O (n 2):
- Сортировка массива в порядке возрастания. Это берет O (n log n).
-
Теперь рассмотрим каждый элемент a [i]. Если a [i] = a [j] + a [k], то, поскольку числа положительны и массив теперь отсортирован, k < я и j < i.
Чтобы найти такие индексы, запустите цикл, который увеличивает j от 1 до i и уменьшает k от i до 0 в то же самое время, пока не встретится. Увеличьте j, если a[j]+a[k] < a[i], и уменьшите k, если сумма больше, чем a[i]. Если сумма равна, то один из ответов, напечатайте ее и сдвиньте оба индекса.
Это выполняет операции O (i).
- Повторите шаг 2 для каждого индекса
i. Таким образом вам понадобятся полностью операции O (n 2), которые будут окончательной оценкой.
Ответ 2
Никто не знает, как сделать значительно лучше, чем квадратичный для тесно связанной проблемы 3SUM (http://en.wikipedia.org/wiki/3SUM). Я бы оценил возможность быстрого решения вашей проблемы как маловероятного.
Задача 3SUM заключается в нахождении a + b + c = 0. Пусть PYTHTRIP является задачей нахождения a 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. Остальная часть доказательства проста.
Ответ 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
Ответ 4
Не уверен, что это лучше, но вы можете вычислить их во времени, пропорциональном максимальному значению в списке, просто вычислив все возможные тройки, меньшие или равные ему. Следующий код 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}));
}
}
}
}
Ответ 5
Вот решение, которое может масштабироваться лучше для больших списков небольших чисел. По крайней мере, он отличается: 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)) total.
Окончательный анализ: O (N ((sqrt M/log M) + (log N * log M))), N = размер массива, M = величина значений.
(* Чтобы принять 64-битный ввод, существуют 323-разрядные простые числа 203M, но мы можем использовать таблицу различий в один байт per prime, так как различия все четные и, возможно, также генерируют большие простые числа в последовательности по требованию. Чтобы принять 32-битный ввод, необходима таблица из 16-разрядных простых чисел, которая достаточно мала, чтобы вписаться в кеш L1. Время здесь - это переоценка, предполагающая, что все простые коэффициенты меньше квадратного корня.)
(** Фактическая граница ниже из-за повторяющихся простых факторов.)
Ответ 6
Некоторым из моих сотрудников была задана эта же проблема в учебном курсе 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;
}
Ответ 7
Решение в O (N).
- узнать минимальный элемент в массиве. min O (n).
- узнать максимальный элемент в массиве. max O (n).
- сделать hastable элементов, чтобы элемент можно было искать в O (1).
- m ^ 2-1 = min.... положить min из шага 1. найти m в этом уравнении. O (1)
- 2m = min.... поставьте min из шага 1. найдите m в этом уравнении. O (1)
-
m ^ 2 + 1 = max.... положим max из шага 2. найдите m в этом уравнении. O (1)
-
выберите пол минуты (шаги 4,5,6), скажем, minValue.O(1)
-
выберите ceil max (шаги 4,5,6), скажем maxValue.O(1)
-
цикл от j = minValue до maxValue. maxvalue-minvalue будет меньше, чем корень N.
9. вычислим три числа j ^ 2-1,2j, j ^ 2 + 1.
9.b искать эти цифры в хэш-таблице. если найден возврат успеха.
- Ошибка возврата.
Ответ 8
Если (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)
Сообщите мне, если это не совсем то, что вы ищете.
Ответ 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 ([email protected])
*/
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);
}
}
Ответ 10
Это можно сделать в O (n) времени. сначала хэш-элементы на карте для проверки существования. после этого примените приведенный ниже алгоритм
Сканирование массива, и если элемент является четным числом, (n, n ^ 2/2 +1, n ^ 2/2 -1) является тройкой, которую можно найти. просто проверьте это существование с помощью поиска хэш-карт. если все элементы в триплете существуют, напечатайте триплет.
Ответ 11
Здесь реализация в Java:
/**
* Step1: Square each of the elements in the array [O(n)]
* Step2: Sort the array [O(n logn)]
* Step3: For each element in the array, find all the pairs in the array whose sum is equal to that element [O(n2)]
*
* Time Complexity: O(n2)
*/
public static Set<Set<Integer>> findAllPythogoreanTriplets(int [] unsortedData) {
// O(n) - Square all the elements in the array
for (int i = 0; i < unsortedData.length; i++)
unsortedData[i] *= unsortedData[i];
// O(n logn) - Sort
int [] sortedSquareData = QuickSort.sort(unsortedData);
// O(n2)
Set<Set<Integer>> triplets = new HashSet<Set<Integer>>();
for (int i = 0; i < sortedSquareData.length; i++) {
Set<Set<Integer>> pairs = findAllPairsThatSumToAConstant(sortedSquareData, sortedSquareData[i]);
for (Set<Integer> pair : pairs) {
Set<Integer> triplet = new HashSet<Integer>();
for (Integer n : pair) {
triplet.add((int)Math.sqrt(n));
}
triplet.add((int)Math.sqrt(sortedSquareData[i])); // adding the third element to the pair to make it a triplet
triplets.add(triplet);
}
}
return triplets;
}
public static Set<Set<Integer>> findAllPairsThatSumToAConstant(int [] sortedData, int constant) {
// O(n)
Set<Set<Integer>> pairs = new HashSet<Set<Integer>>();
int p1 = 0; // pointing to the first element
int p2 = sortedData.length - 1; // pointing to the last element
while (p1 < p2) {
int pointersSum = sortedData[p1] + sortedData[p2];
if (pointersSum > constant)
p2--;
else if (pointersSum < constant)
p1++;
else {
Set<Integer> set = new HashSet<Integer>();
set.add(sortedData[p1]);
set.add(sortedData[p2]);
pairs.add(set);
p1++;
p2--;
}
}
return pairs;
}
Ответ 12
если проблема такова: "Для массива целых чисел найдутся все тройки такие, что a ^ 2 + b ^ 2 = c ^ 2
Сортировка массива в порядке возрастания
Установите три указателя p1, p2, p3 на позиции 0,1,2
установите pEnd на последнюю запись в массиве
while (p2 < pend-2)
{
sum = (*p1 * *p1 + *p2 * *p2)
while ((*p3 * *p3) < sum && p3 < pEnd -1)
p3++;
if ( *p3 == sum)
output_triple(*p1, *p2, *p3);
p1++;
p2++;
}
он перемещает 3 указателя на массив, так что O (sort (n) + n)
это не n2, потому что следующий проход начинается с следующего наибольшего числа и не reset.
если последнее число было слишком маленьким для тройки, оно все еще мало, когда вы переходите к следующим большим a и b
Ответ 13
public class FindPythagorusCombination {
public static void main(String[] args) {
int[] no={1, 5, 3, 4, 8, 10, 6 };
int[] sortedno= sorno(no);
findPythaComb(sortedno);
}
private static void findPythaComb(int[] sortedno) {
for(int i=0; i<sortedno.length;i++){
int lSum=0, rSum=0;
lSum= sortedno[i]*sortedno[i];
for(int j=i+1; j<sortedno.length; j++){
for(int k=j+1; k<sortedno.length;k++){
rSum= (sortedno[j]*sortedno[j])+(sortedno[k]*sortedno[k]);
if(lSum==rSum){
System.out.println("Pythagorus combination found: " +sortedno[i] +" " +sortedno[j]+" "+sortedno[k]);
}else
rSum=0;
}
}
}
}
private static int[] sorno(int[] no) {
for(int i=0; i<no.length;i++){
for(int j=i+1; j<no.length;j++){
if(no[i]<no[j]){
int temp= no[i];
no[i]= no[j];
no[j]=temp;
}
}
}
return no;
}
}
Ответ 14
import java.io.*;
import java.lang.*;
import java.util.*;
class PythagoreanTriplets
{
public static void main(String args[])throws IOException
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int arr[] = new int[n];
int i,j,k,sum;
System.out.println("Enter the numbers ");
for(i=0;i<n;i++)
{
arr[i]=Integer.parseInt(br.readLine());
arr[i]=arr[i]*arr[i];
}
Arrays.sort(arr);
for(i=n-1;i>=0;i--)
{
for(j=0,k=i-1;j<k;)
{
sum=arr[j]+arr[k];
if(sum==arr[i]){System.out.println((int)Math.sqrt(arr[i]) +","+(int)Math.sqrt(arr[j])+","+(int)Math.sqrt(arr[k]));break;}
else if(sum>arr[i])k--;
else j++;
}
}
}
}
Ответ 15
Поиск пифагорейских триплетов в O (n)
Алгоритм:
- Для каждого элемента массива проверьте его простое или нет
- если он является простым, вычислить другие два числа как ((n ^ 2) +1)/2 и ((n ^ 2) -1)/2 и проверить, находятся ли эти два рассчитанных числа в массиве
- если он не является простым, вычислите другие два числа, как указано в другом случае в коде, приведенном ниже
-
Повторяйте до достижения конца массива
int arr[]={1,2,3,4,5,6,7,8,9,10,12,13,11,60,61};
int prim[]={3,5,7,11};//store all the prime numbers
int r,l;
List<Integer> prime=new ArrayList<Integer>();//storing in list,so that it is easy to search
for(int i=0;i<4;i++){
prime.add(prim[i]);
}
List<Integer> n=new ArrayList<Integer>();
for(int i=0;i<arr.length;i++)
{
n.add(arr[i]);
}
double v1,v2,v3;
int dummy[]=new int[arr.length];
for(int i=0;i<arr.length;i++)
dummy[i]=arr[i];
Integer x=0,y=0,z=0;
List<Integer> temp=new ArrayList<Integer>();
for(int i=0;i<arr.length;i++)
{
temp.add(arr[i]);
}
for(int j:n){
if(prime.contains(j)){//if it is prime
double a,b;
v1=(double)j;
v2=Math.ceil(((j*j)+1)/2);
v3=Math.ceil(((j*j)-1)/2);
if(n.contains((int)v2) && n.contains((int)v3)){
System.out.println((int)v1+" "+(int)v2+" "+(int)v3);
}
}
else//if it is not prime
{
if(j%3==0){
x=j;
y=4*(j/3);
z=5*(j/3);
if(temp.contains(y) && temp.contains(z)){
System.out.println(x+" "+y+" "+z);
//replacing those three elements with 0
dummy[temp.indexOf(x)-1]=0;
dummy[temp.indexOf(y)-1]=0;
dummy[temp.indexOf(z)-1]=0;
}
}
}//else end
}//for end
Сложность: O (n)
