Étant donné un tableau de n entiers et un nombre X donné, trouvez toutes les paires uniques d'éléments (a, b), dont la sommation est égale à X.
Ce qui suit est ma solution, c'est O (nLog (n) + n), mais je ne sais pas si elle est optimale ou non.
int main(void)
{
int arr [10] = {1,2,3,4,5,6,7,8,9,0};
findpair(arr, 10, 7);
}
void findpair(int arr[], int len, int sum)
{
std::sort(arr, arr+len);
int i = 0;
int j = len -1;
while( i < j){
while((arr[i] + arr[j]) <= sum && i < j)
{
if((arr[i] + arr[j]) == sum)
cout << "(" << arr[i] << "," << arr[j] << ")" << endl;
i++;
}
j--;
while((arr[i] + arr[j]) >= sum && i < j)
{
if((arr[i] + arr[j]) == sum)
cout << "(" << arr[i] << "," << arr[j] << ")" << endl;
j--;
}
}
}
while((arr[i] + arr[j]) <= sum && i < j)
devrait êtrewhile( i < J && arr[i] + arr[j] <= sum )
. (similaire pour la deuxième sous-boucle)Réponses:
la source
arr=[1,2,1,2,1,2,1,...]
. Pour l'unicité par valeur, il semble qu'une autre table de hachage indexée par une paire de valeurs ferait l'affaire. Encore une réponse agréable, compacte et élégante. +1hash(K - arr[i]) != i
Vérifie- t-il en quelque sorte à la fois la présence et l'absence de correspondance? Je m'attendrais à ce qu'il y ait un contrôle de présence séparé.Il existe 3 approches pour cette solution:
Soit la somme T et n la taille du tableau
Approche 1:
La manière naïve de procéder serait de vérifier toutes les combinaisons (n choisissez 2). Cette recherche exhaustive est O (n 2 ).
Approche 2:
Une meilleure façon serait de trier le tableau. Cela prend O (n log n)
Ensuite, pour chaque x du tableau A, utilisez la recherche binaire pour rechercher Tx. Cela prendra O (nlogn).
Donc, la recherche globale est O (n log n)
Approche 3:
La meilleure façon serait d'insérer chaque élément dans une table de hachage (sans tri). Cela prend O (n) comme insertion à temps constant.
Ensuite, pour chaque x, nous pouvons simplement rechercher son complément, Tx, qui est O (1).
Globalement, le temps d'exécution de cette approche est O (n).
Vous pouvez en référer plus ici .Merci.
la source
Implémentation en Java: Utilisation de l'algorithme de codaddict (Peut-être légèrement différent)
Pour input =
{2,45,7,3,5,1,8,9}
et si Sum est10
Paires de sortie:
Quelques notes sur la solution:
la source
put(k-input[i], input[i])
(codaddicts met l'index comme valeur, ce qui est utile.) Ce que vous avez écrit peut être simplifié enfor (i:input){ if (intSet.contains(sum-i) { print(i + "," + (sum-i) ); } else {intSet.add(i)}
Solution en java. Vous pouvez ajouter tous les éléments String à un ArrayList de chaînes et renvoyer la liste. Ici, je suis juste en train de l'imprimer.
la source
Implémentation Python:
Production:
la source
C ++ 11, complexité d'exécution O (n):
la source
Voici une solution qui prend en compte les doublons. Il est écrit en javascript et suppose que le tableau est trié. La solution s'exécute en temps O (n) et n'utilise aucune mémoire supplémentaire en dehors de la variable.
J'ai résolu ce problème lors d'une interview pour une grande entreprise. Ils l'ont pris mais pas moi. Alors voilà pour tout le monde.
Commencez des deux côtés de la matrice et avancez lentement vers l'intérieur en vous assurant de compter les doublons s'ils existent.
Il ne compte que les paires mais peut être retravaillé pour
Prendre plaisir!
la source
if(distI > distK) while(_arr[++i]==curI); else while(_arr[--k]==curK);
Sur)
Méthodologie: a + b = c, donc au lieu de chercher (a, b) on cherche a = c - b
la source
Implémentation en Java: Utilisation de l'algorithme de codaddict:
Production:
Si vous voulez des paires dupliquées (par exemple: 80,80), supprimez simplement && (Integer) mapping.get (ka [i])! = I de la condition if et vous êtes prêt à partir.
la source
Je viens de participer à cette question sur HackerRank et voici ma solution `` Objectif C '' :
J'espère que ça aide quelqu'un.
la source
c'est l'implémentation de O (n * lg n) utilisant l'implémentation de la recherche binaire dans une boucle.
la source
En python
la source
Belle solution de Codeaddict. J'ai pris la liberté d'en implémenter une version en Ruby:
Pour autoriser les doublons (1,5), (5,1), il suffit de supprimer l'
&& !result[sum-l]
instructionla source
Voici le code Java pour trois approches:
1. En utilisant Map O (n), HashSet peut également être utilisé ici.
2. Triez le tableau et utilisez BinarySearch pour rechercher le complément O (nLog (n))
3. BruteForce traditionnel à deux boucles O (n ^ 2)
la source
Un programme simple en java pour les tableaux ayant des éléments uniques:
la source
Un simple extrait de code Java pour imprimer les paires ci-dessous:
la source
Une autre solution dans Swift: l'idée est de créer un hachage qui stocke les valeurs de (sum - currentValue) et de le comparer à la valeur actuelle de la boucle. La complexité est O (n).
la source
Ma solution - Java - Sans doublons
la source
Cela imprime les paires et évite les doublons en utilisant la manipulation au niveau du bit.
la source
J'ai contourné la manipulation des bits et j'ai juste comparé les valeurs d'index. C'est moins que la valeur d'itération de la boucle (i dans ce cas). Cela n'imprimera pas les paires en double et les éléments du tableau en double également.
la source
en C #:
la source
Une solution peut être celle-ci, mais pas optimul (la complexité de ce code est O (n ^ 2)):
la source
Une version python simple du code qui trouve une somme de paires de zéro et peut être modifiée pour trouver k:
La complexité d'exécution de la fonction est également O (n) et Space: O (n).
la source
la source
la solution inférieure à o (n) sera =>
la source
Solution en Python utilisant la compréhension de liste
O (N 2 )
donne également deux paires ordonnées - (a, b) et (b, a)
la source
I am not sure … Thanks for comments
). Vous pourriez désigner le coup de pinceau à la complexité plus proche de O (n²).Je peux le faire en O (n). Faites-moi savoir quand vous voulez la réponse. Notez qu'il s'agit simplement de parcourir le tableau une fois sans tri, etc ... Je dois également mentionner qu'il exploite la commutativité de l'addition et n'utilise pas de hachage mais gaspille de la mémoire.
en utilisant le système; using System.Collections.Generic;
/ * Une approche O (n) existe en utilisant une table de recherche. L'approche consiste à stocker la valeur dans un "bac" qui peut être facilement recherché (par exemple, O (1)) s'il s'agit d'un candidat pour une somme appropriée.
par exemple,
pour chaque a [k] du tableau, nous plaçons simplement le it dans un autre tableau à l'emplacement x - a [k].
Supposons que nous ayons [0, 1, 5, 3, 6, 9, 8, 7] et x = 9
Nous créons un nouveau tableau,
index valeur
ALORS, les seules valeurs qui comptent sont celles qui ont un index dans la nouvelle table.
Donc, disons que lorsque nous atteignons 9 ou égal, nous voyons si notre nouveau tableau a l'indice 9 - 9 = 0. Puisqu'il sait que toutes les valeurs qu'il contient s'ajouteront à 9. (notez dans cette cause il est évident qu'il n'y a que 1 possible mais il peut contenir plusieurs valeurs d'index que nous devons stocker).
Donc, ce que nous finissons par faire, c'est de n'avoir à parcourir le tableau qu'une seule fois. Parce que l'addition est commutative, nous obtiendrons tous les résultats possibles.
Par exemple, lorsque nous arrivons à 6, nous obtenons l'index dans notre nouvelle table sous la forme 9 - 6 = 3. Puisque la table contient cette valeur d'index, nous connaissons les valeurs.
Il s'agit essentiellement de troquer la vitesse contre la mémoire. * /
la source
Solution Javascript:
la source
https://github.com/clockzhong/findSumPairNumber
Je l'ai fait sous un coût de complexité O (m + n) pour le temps et l'espace mémoire. Je soupçonne que c'est le meilleur algorithme à ce jour.
la source
int [] arr = {1,2,3,4,5,6,7,8,9,0};
var z = (de a dans arr de b dans arr où 10 - a == b sélectionner nouveau {a, b}). ToList;
la source