La question à la main est la suivante:
q8. donné un tableau non formé A []. La tâche consiste à imprimer toutes les paires uniques dans le tableau non formé avec une somme égale. Considérons l'entrée: A [] = {6, 4, 12, 10, 22, 54, 32, 42, 21, 11} Voici ma solution au problème ci-dessus (en C): Ma logique est à prendre Un élément à la fois et prend sa somme avec tous les autres éléments et pour chaque itération, comparez la somme de deux autres paires d'éléments uniques.
Par exemple, quand i = 0, j = 3, arr [i] + arr [j] = 16. Lorsque k = 1, l = 2, arr [k] + arr [l] = 16. Étant donné que les paires sont uniques (6,10) et (4,12) et leur somme est égale, je les imprime.
Notez que les paires sont supposées être des paires non ordonnées de sorte que (A, B) soit la même que (B, A) et nous n'avons donc pas besoin de répéter cela, car ils doivent être uniques. Ma question est la suivante: je sais que mon code est presque O (n ^ 4). Comment puis-je améliorer / l'optimiser davantage?
Expliquez l'approche de la résolution du problème ci-dessus et d'écrire le code dans une langue de programmation C / C ++ / Python / Java. Quelle est la complexité de temps du problème ci-dessus?
5 Réponses :
Tout d'abord, vous précalcompute la somme de chaque paire et conserve le résultat dans une matrice Suivant, vous en boucle sur le Vous avez donc réduit le gros problème à un plus petit, dans lequel vous vérifiez l'égalité de 2 chiffres, pas de 2 sommes de 2 sommets. < p> Pour cela, vous conservez un vecteur Pour exemple, Vous pouvez également envisager dans paires . paire et voir où 2 entrées sont similaires. paire dans lequel at indice x vous conservez les entrées dans paires où la somme était x < /code >. paire (10) = {{0, 1}} . paire Seule la matrice au-dessus de la diagonale, pour laquelle les index i> j .
Est-ce en python? Je veux une réponse c.
@Divyanshuvarma C'est l'algorithme. C'est la logique. En fonction de la langue que vous utilisez, écrivez-la par conséquent. Par paire (i, j), je veux dire un groupe C de dimension 2. Dans C, vous l'écrivez la paire [i] [j] par exemple.
@Divyanshuvarma Stackoverflow n'est pas une plate-forme pour résoudre les devoirs. Si vous avez besoin de telles plateformes, je vous suggère de Freelancer.com.
C code C pour calculer toutes les sommes et stocker les sommes avec des index dans une gamme de structures. Ensuite, nous trions les structures et impriment des éléments de structure adjacents avec la même somme. Le résultat que j'ai obtenu est:
Calcul des coefficients binomiaux C ( n , k ) via des facteurs facteurs est sujette à débordement. Si taille_t a 64 bits, cela se produira si n > 20. Vous pouvez utiliser c ( n , 2) = n < / I> · ( N - 1) / 2, qui est également évident de vos boucles imbriquées.
Il serait plus facile en C ++, Python ou Java, car ces langues fournissent des conteneurs de haut niveau. En Python, vous pouvez utiliser un alors vous devez uniquement traiter des paires uniques (n < sup> 2 / 2) Il sera légèrement plus complexe en C parce que vous n'avez pas la dicte directe de haut niveau. Si vous pouvez gaspiller une certaine mémoire et que vous n'avez que de petits nombres comme ici, vous pouvez dire que la somme la plus élevée sera inférieure à deux fois le plus grand nombre de la matrice d'entrée et affectera directement une matrice de cette taille. De cette façon, vous garantissez un accès direct à partir d'une somme. De là, vous utilisez simplement une liste liée des paires et c'est tout. En tant que bonus, vous obtenez même une liste triée de SUMS. I Vous ne pouvez pas supposer que les chiffres sont petits, vous devrez construire un conteneur d'accès direct. Un conteneur de type de hachage utilisant N * N / 2 comme taille (n étant la longueur d'A) et la taille de la somme de somme en tant que fonction de hachage doit suffire. Pour complétude, voici un code C possible ne faisant pas la Assomption de petit chiffre (ce code affiche toutes les paires non seulement celles avec des sommes dupliquées): defaultDict (liste) où la clé serait la somme et la valeur une liste des paires donnant cette somme.
"La somme la plus élevée sera inférieure à deux fois le plus grand nombre ..." Donc, dans le cas de la matrice donnée, vous dites que je peux faire un tableau de 96 éléments ou 108? Veuillez également expliquer cela "de cette façon, vous garantissez un accès direct à partir d'une somme. À partir de là, vous utilisez simplement une liste liée des paires et c'est tout." Si je fais un tableau, alors pourquoi une liste liée des paires?
@Divyanshuvarma: Parce que plusieurs paires peuvent donner la même somme. J'utilise donc une liste liée pour enregistrer toutes les paires donnant une somme donnée. Pour la somme la plus élevée, il est trivial de trouver la valeur la plus élevée dans un tableau, mais la recherche des 2 valeurs les plus hautes est un peu plus complexe. Donc, pour la paresseuse, j'utiliserais un éventail de taille 108 lorsque 96 suffisent.
Il peut être fait dans O (n ^ 2 * log (n ^ 2) * m), où M est le nombre maximum de paires (i, j) qui ont la même somme, donc dans le pire des cas O (n ^ 3 * journal (n)).
laisse itérer pour chaque paire 0 <= i, j Vous n'avez pas à vous soucier des paires suivantes à (i, J) qui ont la somme parce que les paires suivantes quand elles sont traitées, elles le compteront.
Voici une solution Java:
import java.util.*;
class Duplicate {
public static void main(String[] args) {
int [] a = {5,3,1,4,5,6,3,7,0,10,6,4,9,1};
List<Integer> li = new ArrayList<Integer>();
int p1=0, p2=0;
for(int i=0; i<a.length;i++) {
for(int j=i+1; j<a.length;j++){
if(a[i]+a[j] == 10) {
p1 = a[i];
p2 = a[j];
if(!li.contains(Math.abs(p2-p1))) {
li.add(Math.abs(p2-p1));
System.out.println("Pairs" + ":" + p1 + "," + p2);
}
}
p1=0;
p2=0;
}
}
}
}
S'il vous plaît écrivez la description comme texte aussi, pas d'images.
Une approche serait de construire une cache de sommes de paires, ainsi que des paires qui font cette somme. Ensuite, il s'agit d'ordonner la mise en cache des sommes et de retirer les résultats. C'est presque trivial en C ++. L'algorithme est O (n * n)
@Bathsheba peut-il être fait en C aussi? Si oui, une idée de la manière dont je peux implémenter cela?
Le faire en C est plus difficile. Votre point de départ est de définir un
struct sur les lignes que j'ai déjà mentionnées. Ensuite, un tableau de cesstruct s. Puis transmettez cette chose dansqsort (la fonction de rappel est le bit amusant).Utilisez un dictionnaire ou une structure de données cartographique, avec la somme en tant que clé et la liste des paires produisant cette somme en tant que valeur (ou simplement une liste de premier numéro de paire, car le deuxième numéro est la somme moins moins ...).
Peut-être que j'ai mal compris la signification de "paire unique", mais il me semble que cet algorithme ne fonctionne pas. Si
int arr [] = {6,4,6,4}; La sortie est(6,4), (4,6) (6,4), (6,4) ) (6,4), (4,6) (6,4), (6,4) (4,6), (6,4) est-ce que la production attendue? N'est pas (6,4) la même chose que (4,6)? La même "solution" peut-elle être imprimée plusieurs fois?arr [i] + arr [J] peut être calculé avant la boucle de k. Ceci est une optimisation mineure.
@ 4386427 L'algorithme suppose que l'entrée ne contient pas de doublons.
Ok ... mais que diriez-vous de la description du problème? Où dit-il que le tableau n'a pas de duplicats?