arrays - unidimensional - encontrar un par de números en el conjunto que se suman a la suma dada
programacion ats c++ vectores (19)
Pregunta: Dado un conjunto desordenado de enteros positivos, ¿es posible encontrar un par de enteros de ese conjunto que sumen una suma determinada?
Restricciones: Esto debe hacerse en O (n) y en contexto (sin ningún tipo de almacenamiento externo como arreglos, hash-maps) (puede usar variables / punteros adicionales)
Si esto no es posible, ¿puede haber una prueba para el mismo?
- Use la clasificación de recuento para ordenar la matriz O (n).
tomar dos punteros uno comienza desde el 0 ° índice de la matriz, y otro desde el final de la matriz decir (n-1).
ejecutar el ciclo hasta que sea bajo <= alto
Sum = arr[low] + arr[high] if(sum == target) print low, high if(sum < target) low++ if(sum > target) high--El paso 2 a 10 toma el tiempo de O (n), y la ordenación de conteo toma O (n). Entonces, la complejidad del tiempo total será O (n).
AS @PengOne mencionó que no es posible en el esquema general de las cosas. Pero si haces algunas restricciones en los datos de i / p.
- todos los elementos son todos + o todos -, si no, necesitaría conocer el rango (alto, bajo) y los cambios realizados.
- K, la suma de dos enteros es escasa en comparación con los elementos en general.
- Está bien destruir la matriz i / p A [N].
Paso 1: Mueva todos los elementos inferiores a SUM al comienzo de la matriz; por ejemplo, en N Passes, hemos dividido la matriz en [0, K] y [K, N-1] de manera que [0, K] contenga elementos <= SUMA.
Paso 2: dado que conocemos los límites (0 a SUM) podemos usar el orden de radix.
Paso 3: utilice la búsqueda binaria en A [K], una cosa buena es que si necesitamos encontrar un elemento complementario, solo necesitamos ver la mitad de la matriz A [K]. entonces en A [k] iteramos sobre A [0 a K / 2 + 1] tenemos que hacer una búsqueda binaria en A [i a K].
Tan total appx. el tiempo es, N + K + K / 2 lg (K) donde K es el número de elementos por cierto 0 a Suma en i / p A [N]
Nota: si usas el enfoque de @ PengOne puedes hacer el paso 3 en K. Así que el tiempo total sería N + 2K, que es definitivamente O (N)
No usamos ninguna memoria adicional, pero destruimos la matriz i / p, que tampoco está mal, ya que no tenía ningún orden para empezar.
Aquí hay un algoritmo O (N). Se basa en un algoritmo de eliminación de duplicados en el lugar O (N) , y la existencia de una buena función hash para los ints en su matriz.
Primero, elimine todos los duplicados de la matriz.
Segundo, revise el conjunto y reemplace cada número x con min (x, Sx) donde S es la suma que desea alcanzar.
En tercer lugar, busque si hay duplicados en la matriz: si ''x'' está duplicada, entonces ''x'' y ''Sx'' deben haber ocurrido en la matriz original, y ha encontrado su par.
Aquí hay una solución en 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
Aquí hay una solución que toma en cuenta las entradas duplicadas. Está escrito en javascript y se ejecuta con matrices ordenadas y no ordenadas. La solución se ejecuta en O (n) tiempo.
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<k) {
asc_arr[_arr[i]]=-(~(asc_arr[_arr[i]]));
asc_arr[_arr[k]]=-(~(asc_arr[_arr[k]]));
i++;
k--;
}
// odd amount of elements
if(i==k) {
asc_arr[_arr[k]]=-(~(asc_arr[_arr[k]]));
k--;
}
// count all the pairs reducing tallies as you go
while(i<len||k>-1){
var y;
if(i<len){
y = x-_arr[i];
if(asc_arr[y]!=undefined&&(asc_arr[y]+asc_arr[_arr[i]])>1) {
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;
}
Comience en ambos lados de la matriz y avance lentamente hacia adentro, manteniendo un recuento de cuántas veces se encuentra cada número. Una vez que alcanzas el punto medio, todos los números son contados y ahora puedes avanzar ambos punteros contando los pares sobre la marcha.
Solo cuenta pares, pero se puede volver a trabajar para
- encuentra los pares
- encontrar pares <x
- buscar pares> x
¡Disfrutar!
El siguiente sitio proporciona una solución simple usando hashset que ve un número y luego busca en el hashset el número sum-current dado http://www.dsalgo.com/UnsortedTwoSumToK.php
En Java, esto depende del número máximo en la matriz. devuelve un int [] que tiene los índices de dos elementos. está en).
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;
}
En javascript: Este código cuando n es mayor que el tiempo y el número de iteraciones aumentan. El número de prueba realizado por el programa será igual a ((n * (n / 2) + n / 2) donde n es el número de elementos. El número de suma dado se descarta en if (arr [i] + arr [j ] === 0) donde 0 podría ser cualquier número dado.
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));
Esto podría ser posible si la matriz contiene números, cuyo límite superior conoce de antemano. A continuación, utilice la clase de recuento o ordenación de radix (o (n)) y utilice el algoritmo que sugirió @PengOne.
De lo contrario, no puedo pensar en la solución O (n). Pero la solución O (nlgn) funciona de esta manera: -
Primero ordena la matriz usando el tipo de fusión o clasificación rápida (para inplace). Encuentra si sum - array_element está en esta matriz ordenada. Uno puede usar la búsqueda binaria para eso.
So total time complexity: O(nlgn) + O(lgn) -> O(nlgn).
Implementación 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
La impresión ingenua de doble bucle con rendimiento O (nxn) puede mejorarse con el rendimiento O (n) lineal utilizando la memoria O (n) para la Tabla Hash de la siguiente manera:
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();
}
Me hicieron esta misma pregunta durante una entrevista, y este es el plan que tenía en mente. Queda una mejora por hacer, para permitir números negativos, pero solo sería necesario modificar los índices. El espacio no es bueno, pero creo que el tiempo de ejecución aquí sería O (N) + O (N) + O (subconjunto de N) -> O (N). Puedo estar equivocado.
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<n_numbers;i++){ array_freq[array_numbers[i]]++; } //O(N)
for(i=0; i<n_numbers;i++)
{ //O(N)
if ((array_freq[x-array_numbers[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<freq;i++)
{ //O([size-k subset])
n_numbers+= (freq-i);
}
printf(“-{%d,%d} %d times/n”,x/2,x/2,n_numbers);
}
return;
}else{
return; // Incoming NULL array
printf(“nothing to do here, bad pointer/n”);
}
}
Los críticos son bienvenidos.
Mi solución en Java (Complejidad del tiempo O (n)), esto generará todos los pares con una suma dada
import java.util.HashMap;
import java.util.Map;
public class Test {
public static void main(String[] args) {
// TODO Auto-generated method stub
Map<Integer, Integer> 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]));
}
}
}
}
No garantizado que sea posible; ¿cómo se selecciona la suma dada?
Ejemplo: matriz sin clasificar de enteros
2, 6, 4, 8, 12, 10
Cantidad dada:
7
??
Primero debes encontrar la matriz inversa => suma menos la matriz real y luego verificar si algún elemento de esta nueva matriz existe en la matriz real.
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);
Primero, ordena la matriz usando radix sort . Eso te hará retroceder O (kN). Luego proceda como sugiere @PengOne.
Si tiene una matriz ordenada, puede encontrar dicha pareja en O (n) moviendo dos punteros hacia la mitad
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;
La clasificación se puede hacer O (N) si tiene un límite en el tamaño de los números (o si la matriz ya está ordenada en primer lugar). Incluso entonces, un factor de inicio de sesión n es realmente pequeño y no quiero molestarme en afeitarlo.
prueba:
Si hay una solución (i*, j*) , supongamos, sin pérdida de generalidad, que alcanzo i* antes de que j alcance j* . Dado que para todo j'' entre j* y j sabemos que a[j''] > a[j*] podemos extrapolar que a[i] + a[j''] > a[i*] + a[j*] = target y, por lo tanto, que todos los siguientes pasos del algoritmo harán que j disminuya hasta que alcance j* (o un valor igual) sin darme la oportunidad de avanzar y "perder" la solución.
La interpretación en la otra dirección es similar.
Una solución de espacio O(N) y O(1) que funciona en una matriz ordenada:
Deje que M sea el valor que busca. Use dos punteros, X e Y Comience X=0 al comienzo e Y=N-1 al final. Calcule la suma sum = array[X] + array[Y] . Si sum > M , entonces disminuya Y , de lo contrario, incremente X Si los punteros se cruzan, entonces no existe solución.
Puede ordenar en su lugar para obtener esto para una matriz general, pero no estoy seguro de que haya una solución espacial O(N) y O(1) en general.
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 solución en python