algorithm - son - suma de numeros impares pseint

¿Cómo escribir un algoritmo para verificar si la suma de cualquiera de los dos números en una matriz/lista coincide con un número dado?

Question

¿Cómo puedo escribir un algoritmo para verificar si la suma de cualquiera de los dos números en una matriz / lista coincide con un número dado con una complejidad de nlogn ?

Answer 1

1. Resolvió la pregunta en Swift 4.0
2. Resuelto de 3 formas diferentes (con 2 tipos diferentes de devolución -> Boolean e Índices)

A) TimeComplexity => 0 (n Log n) SpaceComplexity => 0 (n).

B) TimeComplexity => 0 (n ^ 2) SpaceComplexity => 0 (1).

C) TimeComplexity => 0 (n) SpaceComplexity => 0 (n)

3. Elija la Solución A, B o C dependiendo de TradeOff.

   //***********************Solution A*********************//
   //This solution returns TRUE if any such two pairs exist in the array
   func binarySearch(list: [Int], key: Int, start: Int, end: Int) -> Int? { //Helper Function
   
               if end < start {
                   return -1
               } else {
                   let midIndex = (start + end) / 2
   
                   if list[midIndex] > key {
                       return binarySearch(list: list, key: key, start: start, end:  midIndex - 1)
                   } else if list[midIndex] < key {
                       return binarySearch(list: list, key: key, start: midIndex + 1, end: end)
                   } else {
                       return midIndex
                   }
               }
           }
   
           func twoPairSum(sum : Int, inputArray: [Int]) -> Bool {
   
               //Do this only if array isn''t Sorted!
               let sortedArray = inputArray.sorted()
   
               for (currentIndex, value)  in sortedArray.enumerated() {
                   if let indexReturned =  binarySearch(list: sortedArray, key: sum - value, start: 0, end: sortedArray.count-1) {
                       if indexReturned != -1 && (indexReturned != currentIndex) {
                           return true
                       }
                   }
               }
               return false
           }
   
    //***********************Solution B*********************//
    //This solution returns the indexes of the two pair elements if any such two pairs exists in the array
    func twoPairSum(_ nums: [Int], _ target: Int) -> [Int] {
   
               for currentIndex in 0..<nums.count {
                   for nextIndex in currentIndex+1..<nums.count {
                       if calculateSum(firstElement: nums[currentIndex], secondElement: nums[nextIndex], target: target) {
                           return [currentIndex, nextIndex]
                       }
                   }
               }
   
               return []
           }
   
           func calculateSum (firstElement: Int, secondElement: Int, target: Int) -> Bool {//Helper Function
               return (firstElement + secondElement) == target
           }
   
       //*******************Solution C*********************//
      //This solution returns the indexes of the two pair elements if any such two pairs exists in the array
      func twoPairSum(_ nums: [Int], _ target: Int) -> [Int] {
   
               var dict = [Int: Int]()
   
               for (index, value) in nums.enumerated() {
                   dict[value] = index
               }
   
               for (index, value) in nums.enumerated() {
                   let otherIndex = dict[(target - value)]
                   if otherIndex != nil && otherIndex != index {
                       return [index, otherIndex!]
                   }
               }
   
               return []
           }

Answer 2

Aquí hay un algoritmo que se ejecuta en O (n) si la matriz ya está ordenada o O (n log n) si no está ya ordenada. Toma pistas de muchas otras respuestas aquí. El código está en Java, pero aquí hay un pseudo código derivado de muchas respuestas existentes, pero optimizado para duplicados en general

1. Supongo que si los primeros y últimos elementos son iguales al objetivo.
2. Crear un mapa con el valor actual y sus ocurrencias.
3. Cree un conjunto visitado que contenga elementos que ya vimos, esto se optimiza para duplicados como, por ejemplo, con una entrada de (1,1,1,1,1,1,2) y objetivo 4, solo calculamos para 0 y el último elemento y no todos los 1 en la matriz.

4. Utilice estas variables para calcular la existencia del objetivo en la matriz; establezca currentValue en array [ith]; establece newTarget en target - currentValue; establezca expectedCount en 2 si currentValue es igual a newTarget o 1 de lo contrario

   Y devuelve verdadero solo si a. nunca vimos este entero antes Y b. tenemos algún valor para el nuevo destino en el mapa que creamos c. y el recuento del newTarget es igual o mayor que el expectedCount

OTHERWISE repite el paso 4 hasta que lleguemos al final de la matriz y devolvamos falso OTHERWISE;

Como mencioné, el mejor uso posible para una tienda visitada es cuando tenemos duplicados, nunca ayudaría si ninguno de los elementos es duplicado.

Código Java en https://gist.github.com/eded5dbcee737390acb4

Answer 3

Aquí hay un intento en C. Esto no está marcado tarea.

// Assumes a sorted integer array with no duplicates
void printMatching(int array[], int size, int sum)
{
   int i = 0, k = size - 1;
   int curSum;
   while(i < k)
   {
      curSum = array[i] + array[k];
      if(curSum == sum)
      {
         printf("Found match at indices %d, %d/n", i, k);
         i++;k--;
      }
      else if(curSum < sum)
      {
         i++;
      }
      else
      {
         k--;
      }
   }
}

Aquí hay una salida de prueba usando int a[] = { 3, 5, 6, 7, 8, 9, 13, 15, 17 };

Searching for 12..
Found match at indices 0, 5
Found match at indices 1, 3
Searching for 22...
Found match at indices 1, 8
Found match at indices 3, 7
Found match at indices 5, 6
Searching for 4..
Searching for 50..

La búsqueda es lineal, por lo que O (n). El tipo que se lleva a cabo detrás de las escenas será O (n * logn) si utiliza uno de los tipos buenos.

Debido a las matemáticas detrás de Big-O, el término más pequeño en términos aditivos se eliminará de forma efectiva de su cálculo y terminará con O (n logn).

Answer 4

Depende Si desea solo una suma O (N) u O (N log N) o todas las sumas O (N ^ 2) u O (N ^ 2 log N). En este último caso mejor utiliza un FFT>

Answer 5

Digamos que queremos encontrar dos números en la matriz A que cuando se suman igual a N.

1. Ordenar la matriz.
2. Encuentre el número más grande en la matriz que sea menor que N / 2. Establece el índice de ese número como más bajo .
3. Inicializa la parte superior para que sea más baja + 1.
4. Establecer suma = A [ inferior ] + A [ superior ].
5. Si suma == N, hecho.
6. Si suma <N, incrementa la parte superior .
7. Si suma > N, decrementa más abajo .
8. Si inferior o superior está fuera de la matriz, se hace sin ninguna coincidencia.
9. Vuelve a 4.

El ordenamiento se puede hacer en O (n log n). La búsqueda se realiza en tiempo lineal.

Answer 6

Este es O (n)

public static bool doesTargetExistsInList(int Target, int[] inputArray)
{
    if (inputArray != null && inputArray.Length > 0 )
    {
        Hashtable inputHashTable = new Hashtable();

        // This hash table will have all the items in the input array and how many times they appeard
        Hashtable duplicateItems = new Hashtable();

        foreach (int i in inputArray)
        {
            if (!inputHashTable.ContainsKey(i))
            {
                inputHashTable.Add(i, Target - i);
                duplicateItems.Add(i, 1);
            }
            else
            {
                duplicateItems[i] = (int)duplicateItems[i] + 1;    
            }

        }

        foreach (DictionaryEntry de in inputHashTable)
        {
            if ((int)de.Key == (int)de.Value)
            {
                if ((int)duplicateItems[de.Key] > 1)
                return true;
            }
            else if (inputHashTable.ContainsKey(de.Value))
            {
                return true;
            }
        }
    }
    return false;
}

Answer 7

Esto está en Java: Esto incluso elimina los posibles duplicados. Tiempo de ejecución: O(n^2)

private static int[] intArray = {15,5,10,20,25,30};
private static int sum = 35;

private static void algorithm()
{
    Map<Integer, Integer> intMap = new Hashtable<Integer, Integer>();
    for (int i=0; i<intArray.length; i++) 
    {
        intMap.put(i, intArray[i]);
        if(intMap.containsValue(sum - intArray[i]))
            System.out.println("Found numbers : "+intArray[i] +" and "+(sum - intArray[i]));

    }
    System.out.println(intMap);
}

Answer 8

Esto se puede hacer en O(n) usando una tabla hash. Inicialice la tabla con todos los números de la matriz, con el número como la clave y la frecuencia como el valor. Recorra cada número de la matriz y vea si (sum - number) existe en la tabla. Si lo hace, tienes una coincidencia. Después de haber iterado a través de todos los números en la matriz, debe tener una lista de todos los pares que sumen el número deseado.

array = initial array
table = hash(array)
S = sum

for each n in array
    if table[S-n] exists
        print "found numbers" n, S-n

El caso en el que n y la tabla [Sn] se refieren al mismo número dos veces puede tratarse con un control adicional, pero la complejidad sigue siendo O(n) .

Answer 9

Estoy seguro de que hay una mejor manera, pero aquí hay una idea:

1. Ordenar matriz
2. Para cada elemento e en la matriz, búsqueda binaria del complemento (suma - e)

Ambas operaciones son O(n log n) .

Answer 10

Paso 1: Ordenar la matriz en O (n logn)

Paso 2: encontrar dos índices

0 <= i <j <= n en a [0..n] de modo que a [i] + a [j] == k, donde k recibe la clave.

int i=0,j=n;
while(i<j) {
   int sum = a[i]+a[j];
   if(sum == k)
        print(i,j)
   else if (sum < k)
        i++;
   else if (sum > k)
        j--;
}

Answer 11

Utilice una tabla hash . Inserte todos los números en su tabla hash, junto con su índice. Entonces, sea S la suma deseada. Para cada array[i] numérica array[i] en su matriz inicial, vea si S - array[i] existe en su tabla hash con un índice diferente a i .

El caso promedio es O(n) , el peor caso es O(n^2) , así que use la solución de búsqueda binaria si tiene miedo del peor caso.

Answer 12

    public void sumOfTwoQualToTargetSum()
    {
        List<int> list= new List<int>();
        list.Add(1);
        list.Add(3);
        list.Add(5);
        list.Add(7);
        list.Add(9);

        int targetsum = 12;

        int[] arr = list.ToArray();

        for (int i = 0; i < arr.Length; i++)
        {
            for (int j = 0; j < arr.Length; j++)
            {
                if ((i != j) && ((arr[i] + arr[j]) == targetsum))
                {
                    Console.Write("i =" + i);
                    Console.WriteLine("j =" + j);
                }
            }
        }
    }

Answer 13

def sum_in(numbers, sum_):
    """whether any two numbers from `numbers` form `sum_`."""
    a = set(numbers) # O(n)
    return any((sum_ - n) in a for n in a) # O(n)

Ejemplo:

>>> sum_in([200, -10, -100], 100)
True