Ricerca di 2 numeri uguali a 10 [chiuso]

Question

Ricerca di 2 numeri uguali a 10 [chiuso]

#1 da (1 voti)

-2

Durante un'intervista di oggi mi è stato chiesto di scrivere una funzione che accettasse un array di numeri interi e restituisse le posizioni di due valori nella matrice che la somma era 10.

Il mio codice era

C #

public string ReturnIntegers(int[] arrayOfIntegers)
{
   for(int j = 0; j < arrayOfIntegers.Length - 1; j++)
   {
      for(int k = j + 1; k < arrayOfIntegers.Length; k++)
      {
          sum = arrayOfIntegers[j] + arrayOfIntegers[k];
          if(sum == 10)
             return j + "," + k;
      }

}

Supponendo che l'array inserito contenga più di 2 valori. Il mio intervistatore ha detto che questo aveva una magnitudine di n ^ 2 se l'array conteneva un miliardo di valori. Qual è una soluzione migliore (prestazioni) per supportare un numero elevato di valori.

code-quality code-reviews c#

posta Kyle Johnson 21.10.2015 - 22:07

fonte

1 risposta

Leggi altre domande sui tag code-quality code-reviews c#

imposta il nome dell'autore per un codice sorgente biforcato e modificato Argomenti multipli per l'ultimo parametro

score 1 · Answer 1

Qui ci sono davvero due domande

l'algoritmo potrebbe essere implementato in modo migliore / più pulito
c'è un algoritmo migliore.

Due sono le cose che mi hanno fatto saltare in mano. In primo luogo, non c'è nulla da gestire nel caso in cui non ci sia un assolo. La funzione raggiunge la fine senza raggiungere una dichiarazione di ritorno. In alcune lingue questo è un errore di compilazione, in altri dà un comportamento indefinito. Non so su C # in particolare. L'altro è che stai restituendo il risultato come una stringa, che di solito non è un modo molto efficiente di fare le cose.

Riguardo all'algoritmo, l'algoritmo che hai scelto ha una complessità di ordine n². Quindi per le liste di grandi dimensioni sarà lento. D'altra parte non assegna alcuna memoria adizionale / crea nuovi oggetti e per piccole liste mi aspetto che sia in realtà l'assolo più veloce.

Per gli elenchi di grandi dimensioni potrebbe essere meglio fare qualcosa di simile (nota: questo non è testato e io non codifico in c #)

public string ReturnIntegers(int[] arrayOfIntegers)
{
   Dictionary d<int,int> = new Dictionary<int,int>

   for(int j = 0; j < arrayOfIntegers.Length - 1; j++)
   {
      d.add(10-arrayOfIntegers[j]),j)
   }          
   for(int k = 0; k < arrayOfIntegers.Length; k++)
   {
       if (d.ContainsKey(arrayOfIntegers[k])) {
           j = d[arrayOfIntegers[k]]
           return j + "," + k;
       }
   }
   return null;
}