Как найти пифагорейские тройки в массиве быстрее, чем 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

Нахождение пифагорейских триплетов в O (n)

Алгоритм:

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

4. Повторять до тех пор, пока не будет достигнут конец массива

    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)

Answer 2

    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++;

        }
   }

}
}

Answer 3

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;

    }



}

Answer 4

если проблема одна "Для массива целых чисел найдите все тройки, такие что a ^ 2 + b ^ 2 = c ^ 2

Сортировка массива в порядке возрастания

Установить три указателя p1, p2, p3 в записях 0,1,2 установить pEnd для последней записи в массиве

while (p2

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, потому что следующий проход начинается со следующего наибольшего числа и не сбрасывается. если последнее число было слишком маленьким для тройки, оно все еще мало, когда вы переходите к следующему большему a и b

Answer 5

Вот реализация на 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;
}