trova una coppia di numeri nella matrice che aggiunga alla sum data

Domanda: Dato un array non ordinato di numeri interi positivi, è ansible trovare una coppia di numeri interi da quell’array che riassume una data sum?

Vincoli: Questo dovrebbe essere fatto in O (n) e sul posto (senza alcuna memoria esterna come array, hash-maps) (puoi usare variabili extra / puntatori)

Se questo non è ansible, può esserci una prova fornita per lo stesso?

Se hai un array ordinato puoi trovare tale coppia in O (n) spostando due puntatori verso il centro

 i = 0 j = n-1 while(i < j){ if (a[i] + a[j] == target) return (i, j); else if (a[i] + a[j] < target) i += 1; else if (a[i] + a[j] > target) j -= 1; } return NOT_FOUND; 

L’ordinamento può essere reso O (N) se si ha un limite sulla dimensione dei numeri (o se l’array è già ordinato in primo luogo). Anche in questo caso, un fattore log n è molto piccolo e non voglio preoccuparmi di eliminarlo.

prova:

Se c’è una soluzione (i*, j*) , supponiamo, senza perdita di generalità, che i raggiunga i* prima che j raggiunga j* . Poiché per tutti j' tra j* e j sappiamo che a[j'] > a[j*] possiamo estrapolare che a[i] + a[j'] > a[i*] + a[j*] = target e, quindi, che tutti i seguenti passaggi dell’algoritmo causeranno la diminuzione di j fino a raggiungere j* (o un valore uguale) senza dare la possibilità di avanzare in avanti e “perdere” la soluzione.

L’interpretazione nell’altra direzione è simile.

Una soluzione di spazio O(N) e O(1) che funziona su un array ordinato:

Sia M il valore che cerchi. Usa due puntatori, X e Y Inizia X=0 all’inizio e Y=N-1 alla fine. Calcola la sum sum = array[X] + array[Y] . Se sum > M , quindi decrementa Y , altrimenti incrementa X Se i puntatori si incrociano, non esiste alcuna soluzione.

È ansible ordinare per ottenere questo per un array generale, ma non sono sicuro che ci sia un tempo O(N) e una soluzione di spazio O(1) in generale.

Questo potrebbe essere ansible se l’array contiene numeri, il cui limite superiore è noto a priori. Quindi usa il conteggio sort o radix sort (o (n)) e usa l’algoritmo suggerito da @PengOne.

Altrimenti non posso pensare alla soluzione O (n). Ma la soluzione O (nlgn) funziona in questo modo: –

Per prima cosa ordina l’array usando l’ordinamento di unione o l’ordinamento rapido (per l’interno). Trova se sum – array_element è lì in questo array ordinato. Si può usare la ricerca binaria per quello.

 So total time complexity: O(nlgn) + O(lgn) -> O(nlgn). 

AS @PengOne ha detto che non è ansible nello schema generale delle cose. Ma se si apportano alcune restrizioni sui dati i / p.

  1. tutti gli elementi sono tutti + o tutti -, altrimenti non sarebbe necessario conoscere l’intervallo (alto, basso) e apportare modifiche.
  2. K, la sum di due interi è sparsa rispetto agli elementi in generale.
  3. Va bene distruggere l’array i / p A [N].

Passaggio 1: sposta tutti gli elementi meno di SUM all’inizio della matrice, ad esempio in N Passes abbiamo diviso la matrice in [0, K] e [K, N-1] in modo che [0, K] contenga elementi <= SUM.

Passo 2: Poiché conosciamo i limiti (da 0 a SUM), possiamo usare l’ordinamento digitale.

Step 3: Usa la ricerca binaria su A [K], una cosa buona è che se abbiamo bisogno di trovare elementi complementari, dobbiamo solo guardare metà della matrice A [K]. così in A [k] iteriamo su A [da 0 a K / 2 + 1] dobbiamo fare una ricerca binaria in A [i a K].

Quindi appx totale. il tempo è, N + K + K / 2 lg (K) dove K è il numero di elementi btw da 0 a Sum in i / p A [N]

Nota: se usi l’approccio di @ PengOne puoi fare step3 in K. Quindi il tempo totale sarebbe N + 2K che è sicuramente O (N)

Non usiamo alcuna memoria aggiuntiva, ma distruggiamo l’array i / p che non è poi male dato che non aveva alcun ordine per iniziare.

Prima di tutto, ordina l’array usando l’ ordinamento digitale . Questo ti riporterà O (kN). Quindi procedi come suggerito da @PengOne.

Il seguente sito fornisce una soluzione semplice usando hashset che vede un numero e poi cerca l’hashset per il dato numero di sum corrente http://www.dsalgo.com/UnsortedTwoSumToK.php

Ecco un algoritmo O (N). Si basa su un algoritmo di rimozione duplicato O (N) sul posto e sull’esistenza di una buona funzione di hash per gli interi dell’array.

Innanzitutto, rimuovi tutti i duplicati dall’array.

Secondo, passa attraverso l’array e sostituisci ogni numero x con min (x, Sx) dove S è la sum che vuoi raggiungere.

Terzo, trova se ci sono duplicati nell’array: se ‘x’ è duplicato, allora ‘x’ e ‘Sx’ devono essersi verificati nell’array originale e hai trovato la tua coppia.

La mia soluzione in Java (Time Complexity O (n)), produrrà tutte le coppie con una data sum

 import java.util.HashMap; import java.util.Map; public class Test { public static void main(String[] args) { // TODO Auto-generated method stub Map hash = new HashMap<>(); int arr[] = {1,4,2,6,3,8,2,9}; int sum = 5; for (int i = 0; i < arr.length; i++) { hash.put(arr[i],i); } for (int i = 0; i < arr.length; i++) { if(hash.containsKey(sum-arr[i])){ System.out.println(i+ " " + hash.get(sum-arr[i])); } } } } 
  1. Usa il numero di conteggio per ordinare l’array O (n).
  2. prendi due puntatori uno inizia dal 0 ° indice dell’array, e un altro dalla fine dell’array dice (n-1).

    eseguire il ciclo fino a basso <= alto

     Sum = arr[low] + arr[high] if(sum == target) print low, high if(sum < target) low++ if(sum > target) high-- 

    I passaggi da 2 a 10 richiedono O (n) di tempo e il conteggio degli ordinamenti richiede O (n). Quindi la complessità temporale totale sarà O (n).

Ecco una soluzione che tiene conto delle voci duplicate. È scritto in javascript e viene eseguito utilizzando array ordinati e non ordinati. La soluzione viene eseguita in tempo O (n).

 var count_pairs_unsorted = function(_arr,x) { // setup variables var asc_arr = []; var len = _arr.length; if(!x) x = 0; var pairs = 0; var i = -1; var k = len-1; if(len<2) return pairs; // tally all the like numbers into buckets while(i-1){ var y; if(i1) { if(_arr[i]==y) { var comb = 1; while(--asc_arr[_arr[i]] > 0) {pairs+=(comb++);} } else pairs+=asc_arr[_arr[i]]*asc_arr[y]; asc_arr[y] = 0; asc_arr[_arr[i]] = 0; } } if(k>-1) { y = x-_arr[k]; if(asc_arr[y]!=undefined&&(asc_arr[y]+asc_arr[_arr[k]])>1) { if(_arr[k]==y) { var comb = 1; while(--asc_arr[_arr[k]] > 0) {pairs+=(comb++);} } else pairs+=asc_arr[_arr[k]]*asc_arr[y]; asc_arr[y] = 0; asc_arr[_arr[k]] = 0; } } i++; k--; } return pairs; } 

Inizia da entrambi i lati dell’array e procedi lentamente verso l’interno tenendo conto di quante volte ogni numero è stato trovato. Una volta raggiunto il punto centrale, tutti i numeri sono conteggiati e ora puoi progredire entrambi i puntatori contando le coppie man mano che procedi.

Conta solo coppie ma può essere rielaborato per

  • trova le coppie
  • trova le coppie
  • trova coppie> x

Godere!

Implementazione di Ruby

 ar1 = [ 32, 44, 68, 54, 65, 43, 68, 46, 68, 56] for i in 0..ar1.length-1 t = 100 - ar1[i] if ar1.include?(t) s= ar1.count(t) if s < 2 print s , " - " , t, " , " , ar1[i] , " pair ", i, "\n" end end end 

In javascript: questo codice quando n è maggiore, quindi aumentano il tempo e il numero di iterazioni. Il numero di test effettuati dal programma sarà uguale a ((n * (n / 2) + n / 2) dove n è il numero di elementi. Il numero di sum dato viene scartato in if (arr [i] + arr [j ] === 0) dove 0 potrebbe essere qualsiasi numero dato.

 var arr = [-4, -3, 3, 4]; var lengtharr = arr.length; var i = 0; var j = 1; var k = 1; do { do { if (arr[i] + arr[j] === 0) { document.write(' Elements arr [' + i + '] [' + j + '] sum 0'); } else { document.write('____'); } j++; } while (j < lengtharr); k++; j = k; i++; } while (i < (lengtharr-1)); 

Non è garantito che sia ansible; come viene selezionata la sum data?

Esempio: array di numeri interi non ordinati

 2, 6, 4, 8, 12, 10 

Data la sum:

 7 

??

Ecco una soluzione in python:

 a = [9, 8, 9, 2, 15, 11, 21, 8, 9, 2, 2, 8, 9, 2, 15, 11, 21, 8, 9, 2, 9, 8, 9, 2, 15, 11, 21, 8, 9, 2, 2, 8, 9, 2, 15, 11, 2, 8, 9, 2, 2, 8, 9, 2, 15, 11, 21, 8, 9, 12, 2, 8, 9, 2, 15, 11, 21, 7, 9, 2, 23, 8, 9, 2, 15, 11, 21, 8, 9, 2, 2, 12, 9, 2, 15, 11, 21, 8, 9, 2, 2, 8, 9, 2, 15, 11, 21, 8, 9, 2, 2, 8, 9, 2, 15, 11, 21, 8, 9, 2, 2, 8, 9, 2, 15, 11, 21, 8, 9, 2, 2, 7.12, 9, 2, 15, 11, 21, 8, 9, 2, 2, 8, 9, 2, 15, 11, 21, 8, 9, 2, 2, 8, 9, 2, 15, 11, 21, 8, 9, 2, 2, 8, 9, 2, 15, 11, 21, 8, 9, 2, 2, 8, 9, 2, 15, 11, 21, 8, 0.87, 78] i = 0 j = len(a) - 1 my_sum = 8 finded_numbers = () iterations = 0 while(OK): iterations += 1 if (i < j): i += 1 if (i == j): if (i == 0): OK = False break i = 0 j -= 1 if (a[i] + a[j] == my_sum): finded_numbers = (a[i], a[j]) OK = False print finded_numbers print iterations 

Mi è stata fatta questa stessa domanda durante un’intervista, e questo è lo schema che avevo in mente. C’è ancora un miglioramento da fare, per consentire numeri negativi, ma sarebbe solo necessario modificare gli indici. Spazio-saggio non è buono, ma credo che il tempo di esecuzione qui sarebbe O (N) + O (N) + O (sottoinsieme di N) -> O (N). Potrei sbagliarmi.

 void find_sum(int *array_numbers, int x){ int i, freq, n_numbers; int array_freq[x+1]= {0}; // x + 1 as there could be 0's as well if(array_numbers) { n_numbers = (int) sizeof(array_numbers); for(i=0; i 0)&&(array_freq[array_numbers[i]] > 0)&&(array_numbers[i]!=(x/2))) { freq = array_freq[x-array_numbers[i]] * array_freq[array_numbers[i]]; printf(“-{%d,%d} %d times\n”,array_numbers[i],x-array_numbers[i],freq ); // “-{3, 7} 6 times” if there's 3 '7's and 2 '3's array_freq[array_numbers[i]]=0; array_freq[x-array_numbers[i]]=0; // doing this we don't get them repeated } } // end loop if ((x%2)=0) { freq = array_freq[x/2]; n_numbers=0; for(i=1; i 

I critici sono i benvenuti

In Java, questo dipende dal numero massimo di array. restituisce un int [] con gli indici di due elementi. è su).

  public static int[] twoSum(final int[] nums, int target) { int[] r = new int[2]; r[0] = -1; r[1] = -1; int[] vIndex = new int[0Xffff]; for (int i = 0; i < nums.length; i++) { int delta = 0Xfff; int gapIndex = target - nums[i] + delta; if (vIndex[gapIndex] != 0) { r[0] = vIndex[gapIndex]; r[1] = i + 1; return r; } else { vIndex[nums[i] + delta] = i + 1; } } return r; } 

Per prima cosa dovresti trovare array inverso => ​​sum meno matrice effettiva quindi verificare se esiste qualche elemento da questi nuovi array nell’array effettivo.

 const arr = [0, 1, 2, 6]; const sum = 8; let isPairExist = arr .map(item => sum - item) // [8, 7, 6, 2]; .find((item, index) => { arr.splice(0, 1); // an element should pair with another element return arr.find(x => x === item); }) ? true : false; console.log(isPairExist); 

La stampa in doppio ciclo Naïve con prestazioni O (nxn) può essere migliorata con prestazioni O (n) lineari utilizzando la memoria O (n) per la tabella hash come segue:

 void TwoIntegersSum(int[] given, int sum) { Hashtable ht = new Hashtable(); for (int i = 0; i < given.Length; i++) if (ht.Contains(sum - given[i])) Console.WriteLine("{0} + {1}", given[i], sum - given[i]); else ht.Add(given[i], sum - given[i]); Console.Read(); } 
 def pair_sum(arr,k): counter = 0 lookup = set() for num in arr: if k-num in lookup: counter+=1 else: lookup.add(num) return counter pass pair_sum([1,3,2,2],4) 

La soluzione in python