algorithm - repite - Encuentra 2 números en una matriz sin clasificar igual a una suma dada
mostrar numeros repetidos c++ (18)
Necesitamos encontrar pares de números en una matriz cuya suma sea igual a un valor dado.
A = {6,4,5,7,9,1,2}
Suma = 10 Entonces las parejas son - {6,4}, {9,1}
Tengo dos soluciones para esto.
- Una solución O (nlogn): ordene + verifique la suma con 2 iteradores (principio y final).
- Una solución O (n) - hash de la matriz. Luego verifique si
sum-hash[i]existe o no en la tabla hash.
Pero, el problema es que aunque la segunda solución es O (n) tiempo, pero también usa espacio O (n).
Entonces, me preguntaba si podríamos hacerlo en O (n) tiempo y O (1) espacio. ¡Y esto NO es tarea!
Implementación de Python 2.7:
import itertools
list = [1, 1, 2, 3, 4, 5,]
uniquelist = set(list)
targetsum = 5
for n in itertools.combinations(uniquelist, 2):
if n[0] + n[1] == targetsum:
print str(n[0]) + " + " + str(n[1])
Salida:
1 + 4
2 + 3
¿La solución obvia no funciona (se repite en cada par consecutivo) o los dos números están en algún orden?
En ese caso, puede ordenar la lista de números y usar un muestreo aleatorio para dividir la lista ordenada hasta que tenga una lista secundaria lo suficientemente pequeña como para ser iterada.
¿No debería la iteración desde ambos extremos simplemente resolver el problema?
Ordenar la matriz. Y empieza a comparar desde ambos extremos.
if((arr[start] + arr[end]) < sum) start++;
if((arr[start] + arr[end]) > sum) end--;
if((arr[start] + arr[end]) = sum) {print arr[start] "," arr[end] ; start++}
if(start > end) break;
Complejidad del tiempo O(nlogn)
// Implementación de Java usando Hashing import java.io. *;
class PairSum {private static final int MAX = 100000; // Tamaño máximo de Hashmap
static void printpairs(int arr[],int sum)
{
// Declares and initializes the whole array as false
boolean[] binmap = new boolean[MAX];
for (int i=0; i<arr.length; ++i)
{
int temp = sum-arr[i];
// checking for condition
if (temp>=0 && binmap[temp])
{
System.out.println("Pair with given sum " +
sum + " is (" + arr[i] +
", "+temp+")");
}
binmap[arr[i]] = true;
}
}
// Main to test the above function
public static void main (String[] args)
{
int A[] = {1, 4, 45, 6, 10, 8};
int n = 16;
printpairs(A, n);
}
}
Cree un diccionario con la clave de pares (número de la lista) y el valor es el número que es necesario para obtener el valor deseado. A continuación, compruebe la presencia de los pares de números en la lista.
def check_sum_in_list(p_list, p_check_sum):
l_dict = {i: (p_check_sum - i) for i in p_list}
for key, value in l_dict.items():
if key in p_list and value in p_list:
return True
return False
if __name__ == ''__main__'':
l1 = [1, 3, 7, 12, 72, 2, 8]
l2 = [1, 2, 2, 4, 7, 4, 13, 32]
print(check_sum_in_list(l1, 10))
print(check_sum_in_list(l2, 99))
Output:
True
Flase
versión 2
import random
def check_sum_in_list(p_list, p_searched_sum):
print(list(p_list))
l_dict = {i: p_searched_sum - i for i in set(p_list)}
for key, value in l_dict.items():
if key in p_list and value in p_list:
if p_list.index(key) != p_list.index(value):
print(key, value)
return True
return False
if __name__ == ''__main__'':
l1 = []
for i in range(1, 2000000):
l1.append(random.randrange(1, 1000))
j = 0
i = 9
while i < len(l1):
if check_sum_in_list(l1[j:i], 100):
print(''Found'')
break
else:
print(''Continue searching'')
j = i
i = i + 10
Output:
...
[154, 596, 758, 924, 797, 379, 731, 278, 992, 167]
Continue searching
[808, 730, 216, 15, 261, 149, 65, 386, 670, 770]
Continue searching
[961, 632, 39, 888, 61, 18, 166, 167, 474, 108]
39 61
Finded
[Finished in 3.9s]
El código siguiente toma la matriz y el número N como la suma objetivo. Primero se ordena la matriz, luego se toma una nueva matriz que contiene los elementos restantes y luego se analiza no mediante una búsqueda binaria, sino una simple exploración del resto y la matriz simultáneamente.
public static int solution(int[] a, int N) {
quickSort(a, 0, a.length-1); // nlog(n)
int[] remainders = new int[a.length];
for (int i=0; i<a.length; i++) {
remainders[a.length-1-i] = N - a[i]; // n
}
int previous = 0;
for (int j=0; j<a.length; j++) { // ~~ n
int k = previous;
while(k < remainders.length && remainders[k] < a[j]) {
k++;
}
if(k < remainders.length && remainders[k] == a[j]) {
return 1;
}
previous = k;
}
return 0;
}
El siguiente código devuelve verdadero si dos enteros en una matriz coinciden con un entero comparado.
function compareArraySums(array, compare){
var candidates = [];
function compareAdditions(element, index, array){
if(element <= y){
candidates.push(element);
}
}
array.forEach(compareAdditions);
for(var i = 0; i < candidates.length; i++){
for(var j = 0; j < candidates.length; j++){
if (i + j === y){
return true;
}
}
}
}
Esta es una pregunta clásica de la entrevista de Microsoft Research Asia.
Cómo encontrar 2 números en una matriz sin clasificar igual a una suma dada.
[1] solución de fuerza bruta
Este algoritmo es muy simple. La complejidad del tiempo es O (N ^ 2)
[2] Usando búsqueda binaria
Usando bianry search para encontrar el Sum-arr [i] con cada arr [i], la complejidad del tiempo se puede reducir a O (N * logN)
[3] Usando Hash
Sobre la base de [2] algoritmo y uso de hash, la complejidad del tiempo puede reducirse a O (N), pero esta solución agregará el espacio O (N) de hash.
[4] Algoritmo óptimo:
Pseduo-codigo:
for(i=0;j=n-1;i<j)
if(arr[i]+arr[j]==sum) return (i,j);
else if(arr[i]+arr[j]<sum) i++;
else j--;
return(-1,-1);
o
If a[M] + a[m] > I then M--
If a[M] + a[m] < I then m++
If a[M] + a[m] == I you have found it
If m > M, no such numbers exist.
Y, ¿Está esta cuestión completamente resuelta? No. Si el número es N. Este problema será muy complejo.
El quesiton entonces:
¿Cómo puedo encontrar todos los casos de combinación con un número dado?
Este es un problema clásico de NP-Completo que se llama subconjunto-suma.
Para comprender NP / NPC / NP-Hard, es mejor que lea algunos libros profesionales.
Referencias:
[1] http://www.quora.com/Mathematics/How-can-I-find-all-the-combination-cases-with-a-given-number
[2] http://en.wikipedia.org/wiki/Subset_sum_problem
Si asume que el valor M al que se supone que deben sumar los pares es constante y que las entradas en la matriz son positivas, entonces puede hacer esto en un tiempo de pasada ( O(n) ) utilizando los punteros M/2 ( O(1) espacio) de la siguiente manera. Los punteros están etiquetados P1,P2,...,Pk donde k=floor(M/2) . Entonces haz algo como esto
for (int i=0; i<N; ++i) {
int j = array[i];
if (j < M/2) {
if (Pj == 0)
Pj = -(i+1); // found smaller unpaired
else if (Pj > 0)
print(Pj-1,i); // found a pair
Pj = 0;
} else
if (Pj == 0)
Pj = (i+1); // found larger unpaired
else if (Pj < 0)
print(Pj-1,i); // found a pair
Pj = 0;
}
}
Puede manejar entradas repetidas (por ejemplo, dos 6) almacenando los índices como dígitos en la base N , por ejemplo. Para M/2 , puede agregar el condicional
if (j == M/2) {
if (Pj == 0)
Pj = i+1; // found unpaired middle
else
print(Pj-1,i); // found a pair
Pj = 0;
}
Pero ahora tienes el problema de juntar las parejas.
Si los números no son muy grandes, puede usar la transformada rápida de Fourier para multiplicar dos polinomios y luego en O (1) verificar si el coeficiente antes de x ^ (suma necesaria) es mayor que cero. O (n log n) total!
Utilice la ordenación de radix en el lugar y la primera solución de OP con 2 iteradores, uno hacia el otro.
Si los números de la matriz no son algún tipo de números de precisión múltiple y son, por ejemplo, enteros de 32 bits, puede clasificarlos en 2 * 32 pases sin prácticamente espacio adicional (1 bit por pase). O 2 * 8 pases y 16 contadores enteros (4 bits por pase).
Detalles para la solución de 2 iteradores:
El primer iterador apunta inicialmente al primer elemento de la matriz ordenada y avanza. El segundo iterador apunta inicialmente al último elemento de la matriz y avanza hacia atrás.
Si la suma de elementos, a la que hacen referencia los iteradores, es menor que el valor requerido, avance el primer iterador. Si es mayor que el valor requerido, avance el segundo iterador. Si es igual al valor requerido, éxito.
Solo se necesita una pasada, por lo que la complejidad del tiempo es O (n). La complejidad del espacio es O (1). Si se utiliza la ordenación de radix, las complejidades de todo el algoritmo son las mismas.
Si está interesado en problemas relacionados (con la suma de más de 2 números), consulte "Subconjunto de suma con un tamaño de subconjunto fijo" y "Búsqueda de tres elementos en una matriz cuya suma es la más cercana a un número dado" .
si es una matriz ordenada y solo necesitamos un par de números y no todos los pares podemos hacerlo de esta manera:
public void sums(int a[] , int x){ // A = 1,2,3,9,11,20 x=11
int i=0 , j=a.length-1;
while(i < j){
if(a[i] + a[j] == x) system.out.println("the numbers : "a[x] + " " + a[y]);
else if(a[i] + a[j] < x) i++;
else j--;
}
}
1 2 3 9 11 20 || i = 0, j = 5 suma = 21 x = 11
1 2 3 9 11 20 || i = 0, j = 4 suma = 13 x = 11
1 2 3 9 11 20 || i = 0, j = 4 suma = 11 x = 11
FIN
https://github.com/clockzhong/findSumPairNumber
#! /usr/bin/env python
import sys
import os
import re
#get the number list
numberListStr=raw_input("Please input your number list (seperated by spaces).../n")
numberList=[int(i) for i in numberListStr.split()]
print ''you have input the following number list:''
print numberList
#get the sum target value
sumTargetStr=raw_input("Please input your target number:/n")
sumTarget=int(sumTargetStr)
print ''your target is: ''
print sumTarget
def generatePairsWith2IndexLists(list1, list2):
result=[]
for item1 in list1:
for item2 in list2:
#result.append([item1, item2])
result.append([item1+1, item2+1])
#print result
return result
def generatePairsWithOneIndexLists(list1):
result=[]
index = 0
while index< (len(list1)-1):
index2=index+1
while index2 < len(list1):
#result.append([list1[index],list1[index2]])
result.append([list1[index]+1,list1[index2]+1])
index2+=1
index+=1
return result
def getPairs(numList, target):
pairList=[]
candidateSlots=[] ##we have (target-1) slots
#init the candidateSlots list
index=0
while index < target+1:
candidateSlots.append(None)
index+=1
#generate the candidateSlots, contribute O(n) complexity
index=0
while index<len(numList):
if numList[index]<=target and numList[index]>=0:
#print ''index:'',index
#print ''numList[index]:'',numList[index]
#print ''len(candidateSlots):'',len(candidateSlots)
if candidateSlots[numList[index]]==None:
candidateSlots[numList[index]]=[index]
else:
candidateSlots[numList[index]].append(index)
index+=1
#print candidateSlots
#generate the pairs list based on the candidateSlots[] we just created
#contribute O(target) complexity
index=0
while index<=(target/2):
if candidateSlots[index]!=None and candidateSlots[target-index]!=None:
if index!=(target-index):
newPairList=generatePairsWith2IndexLists(candidateSlots[index], candidateSlots[target-index])
else:
newPairList=generatePairsWithOneIndexLists(candidateSlots[index])
pairList+=newPairList
index+=1
return pairList
print getPairs(numberList, sumTarget)
He implementado exitosamente una solución con Python bajo el costo de tiempo y espacio O (n + m). La "m" significa el valor objetivo que la suma de esos dos números necesita igual. Creo que este es el menor costo que podría obtener. Erict2k usó itertools.combinations, también costará un costo de tiempo y espacio similar o superior al comparar mi algoritmo.
public static void Main(string[] args)
{
int[] myArray = {1,2,3,4,5,6,1,4,2,2,7 };
int Sum = 9;
for (int j = 1; j < myArray.Length; j++)
{
if (myArray[j-1]+myArray[j]==Sum)
{
Console.WriteLine("{0}, {1}",myArray[j-1],myArray[j]);
}
}
Console.ReadLine();
}
public void printPairsOfNumbers(int[] a, int sum){
//O(n2)
for (int i = 0; i < a.length; i++) {
for (int j = i+1; j < a.length; j++) {
if(sum - a[i] == a[j]){
//match..
System.out.println(a[i]+","+a[j]);
}
}
}
//O(n) time and O(n) space
Set<Integer> cache = new HashSet<Integer>();
cache.add(a[0]);
for (int i = 1; i < a.length; i++) {
if(cache.contains(sum - a[i])){
//match//
System.out.println(a[i]+","+(sum-a[i]));
}else{
cache.add(a[i]);
}
}
}
`package algorithmsDesignAnalysis;
public class USELESStemp {
public static void main(String[] args){
int A[] = {6, 8, 7, 5, 3, 11, 10};
int sum = 12;
int[] B = new int[A.length];
int Max =A.length;
for(int i=0; i<A.length; i++){
B[i] = sum - A[i];
if(B[i] > Max)
Max = B[i];
if(A[i] > Max)
Max = A[i];
System.out.print(" " + B[i] + "");
} // O(n) here;
System.out.println("/n Max = " + Max);
int[] Array = new int[Max+1];
for(int i=0; i<B.length; i++){
Array[B[i]] = B[i];
} // O(n) here;
for(int i=0; i<A.length; i++){
if (Array[A[i]] >= 0)
System.out.println("We got one: " + A[i] +" and " + (sum-A[i]));
} // O(n) here;
} // end main();
/******
Running time: 3*O(n)
*******/
}
for (int i=0; i < array.size(); i++){
int value = array[i];
int diff = sum - value;
if (! hashSet.contains(diffvalue)){
hashSet.put(value,value);
} else{
printf(sum = diffvalue + hashSet.get(diffvalue));
}
}
--------
Sum being sum of 2 numbers.
public static ArrayList<Integer> find(int[] A , int target){
HashSet<Integer> set = new HashSet<Integer>();
ArrayList<Integer> list = new ArrayList<Integer>();
int diffrence = 0;
for(Integer i : A){
set.add(i);
}
for(int i = 0; i <A.length; i++){
diffrence = target- A[i];
if(set.contains(diffrence)&&A[i]!=diffrence){
list.add(A[i]);
list.add(diffrence);
return list;
}
}
return null;
}