J'ai besoin d'aide pour trouver un algorithme qui trouve:
préfère en pseudo-code ou c, c ++
11 Réponses :
Cela ressemble à des devoirs pour moi. Mais voici ce que je ferais.
Trier d'abord les chiffres (il y a votre n * journal (n)).
Maintenant, créez des pointeurs vers la liste, initiez-le avec les 4 premiers chiffres. Une fois que vous avez cela, vous vérifiez la somme de vos 4 chiffres en cours avec le total. Il devrait être inférieur ou égal à votre somme de recherche (si ce n'est pas le cas, vous pouvez cesser de fumer tôt). Maintenant, tout ce que vous avez à faire est de traverser le reste de votre liste en remplacement alternativement de vos pointeurs avec la valeur actuelle de la liste. Cela n'a besoin que de se produire une fois (ou vraiment au pire 4 fois), il y a donc votre autre N, ce qui fait n ^ 2 * log (n)
Vous devrez garder une trace de certaines logiques pour savoir si vous êtes sur votre somme / sous votre somme et quoi faire ensuite, mais je laisse cela comme votre devoir.
Traverse Rest de votre liste Remplacement alternativement de vos pointeurs avec la valeur actuelle de la liste Cette partie semble extrêmement vague pour moi.
Pouvez-vous donner des détails comment vous traversez la liste avec quatre pointeurs? Laissez-vous le premier pointeur d'abord aller à la fin, puis le second, etc.?
Au fait, ce serait O (n) + O (n * log (n)) = O (n * journal (n)), pas O (n) * O (n * log (n))
Alors, vous voulez dire que cela peut être fait dans O (Nlogn)?
Je ne vais pas répondre à votre question complètement, car je pense que ce sont des devoirs et pensent aussi que cela se passe facilement. Mais je pense que je sais pourquoi vous rencontrez des difficultés avec une réponse, je vais donc vous aider un peu.
Tout d'abord, vous devriez examiner la récursive. Cela signifie appeler une fonction de lui-même.
Deuxièmement, vous devez utiliser une fonction d'assistance, appelée par la fonction que vous souhaitez écrire. Cette fonction devrait prendre comme des arguments: - un tableau de chiffres - la longueur du tableau - la valeur que vous souhaitez trouver des membres qui résument à - le nombre de membres de la matrice que vous souhaitez résumer
Cette fonction sera appelée par votre autre fonction et transmettra un 4 pour le dernier argument. Il s'appellera ensuite ajuster les arguments comme il essaie de trouver des résultats par essai et erreurs partielles.
Sur la pensée en outre, je me suis rendu compte que ce n'est pas O (n ^ 2), comme je l'avais prétendu plus tôt (j'ai mentalement brillant sur les marches moyennes). Il est limité par n ^ 4, mais peut avoir une limite inférieure à celle d'une certaine opportunité à la coupe courte dans de nombreux cas. Je ne crois pas que cette courte coupe l'améliore jusqu'au point de n ^ 2, cependant.
Et comment prouvez-vous la complexité de cela est le cas échéant?
Donc, vous pensez que c'est facile à faire, puis finissez par réaliser que vous ne savez pas comment le faire. Joli. -1.
@IVLAD: J'aurais pu supprimer la réponse et évité un vote en direct, mais j'ai laissé tomber avec une note pointant sur les défauts avec elle.
Merci à tous, après quelques heures aujourd'hui, j'ai atteint des réponses similaires comme vous. Je n'ai pas besoin de tous les numéros possibles, j'ai besoin d'une seule option. Ma solution a également la complexité de O (n ^ 2).
Vous pouvez le faire dans O (n ^ 2). Fonctionne bien avec des nombres dupliqués et négatifs.
hashtable disons, SUMS stockera tous esquives possibles de deux éléments différents. Pour chaque somme s il renvoie une paire d'index i et j tel que a [i] + a [j] == s et i! = j . Mais au départ, il est vide, nous allons le remplir sur le chemin. x = a [1] + a [3] + a [7] + a [3] + A [7 ] + a [10] . Cette somme sera trouvée lorsque i = 7 , j = 10 et repos = a [1] + a [3] (index 1 et 3 sera trouvé à partir de hachage)
Si vous utilisez une carte d'arborescence au lieu d'une hache (qui peut avoir O (n) dans le pire des cas), vous êtes garanti d'avoir O (log n) pour la recherche des sommes. Vous devez également vérifier que vous n'utilisez pas un numéro de plus d'une fois.
@Andre Je ne pense pas que nous devrions considérer le pire temps d'accès au hasch, il est extrêmement improbable de se produire :) Mais si c'est important, Treemap est une solution, oui.
@Andre Vous devez également vérifier que vous n'utilisez pas un numéro de plus d'une fois c'est déjà fait. I et J sont toujours égaux et je
Vous avez raison, je n'ai pas réalisé la façon dont vous mettez à jour la carte des sommes et qu'il ne contient que des indices
Le temps d'exécution demandé me fait penser que les instructeurs s'attendent à autre chose que les tables de hachage. En outre, je ne pense pas que nous ne devrions pas envisager le pire des cas pour les hatupes. Si les chiffres sont assez gros, comment votre solution sera-t-elle taillée pour tous les nombres égaux? Cela fonctionne si vous utilisez des arbres cependant, donc +1.
@IVLAD En fait, nous n'avons besoin que d'une paire pour chaque somme particulière, donc dans le cas de tous les numéros égaux, la haquetable n'aura qu'un seul élément. Il est toujours possible que de nombreuses sommes différentes auront le même hachage, il est difficile d'émuler.
@Nikitarbak +1 belle solution. Supposons prendre un exemple de {2,3,4,5,7,9,10} maintenant lorsque vous = 4 et j = 5, alors courant = 16 et reste = 23-16 = 7 (Supposons x = 23 ici). Noe La carte ne contient que (2,5) mais ne contient pas (4,5). Donc, pour vous débarrasser de la situation, nous pouvons utiliser la somme comme clé et liste comme valeur (afin que plusieurs index puissent être stockés.). Mais si de nombreuses sommes sont égales, notre complexité de temps peut être O (n ^ 3). Ai-je raison? Merci.
@Ecteur dans votre exemple, somme [7] = (3, 0). Donc, vous vous retrouvez avec des index [0, 3, 4, 5]. Je n'ai pas compris la deuxième partie de votre réponse, mais laissez-moi savoir si vous souhaitez plus d'informations.
@Nikitarybak Supposons X = 23. Maintenant, lorsque vous atteignez i = 4 et j = 5 I.e. Courant = 16 et reste = 7. 7 peut être obtenu par un [0] + A [3] et A [1] + A [2]. Mais la carte ne contiendra qu'une seule valeur pour une somme donnée. Donc, il ne contiendra que (0,3) mais ne contiendra pas (1,2). J'espère que cela clarifie.
@Triez-vous, je vois que vous pointez. La définition de problème demande une solution, pas pour toutes les solutions. Vous avez raison de trouver toutes les solutions prendrait plus de temps. Si tous les chiffres sont égaux, il y a des solutions O (n ^ 4), ce qui signifie au moins O (N ^ 4) temps.
Je ne comprends pas comment assurez-vous que vous n'utilisez pas un numéro plus d'une fois? J'ai lu votre commentaire en réponse à André, mais ce n'est toujours pas clair. Pourriez-vous s'il vous plaît élaborer cela?
abuser du fait qu'aucune limite de mémoire n'est spécifiée. Et en utilisant l'approche de division et de conquéralisation habituelle.
Nombre de toutes les permutations pour 4 sous-ensembles est C (N, 4) et est O (n ^ 4). Le nombre de toutes les permutations pour 2 nombres est C (n, 2) et est O (n ^ 2). O (n ^ 2) semble être ok pour la tâche.
A avec n éléments, x .
- Générez toutes les permutations pour 2 sous-ensembles (c'est O (n ^ 2)) et mettez leurs sommes dans le tableau
B avec n ^ 2 éléments (souvenez-vous également des sous-ensembles). Notons comme s [b [i]] le sous-ensemble (composé des deux numéros) dont la somme est b [i] . .
- Trier le
B , O (n ^ 2 * journal (n ^ 2)).
-
traversez le tableau B (o (n ^ 2)) i = [0, n ^ 2) et recherche rapide o ( Journal (n ^ 2)) = O (journal (n)) en elle pour la valeur (x - b [i]) . Il pourrait y avoir plusieurs d'entre eux (mais pas plus que N ^ 2).
4.1. Passer à travers tous les éléments avec la valeur de (x - b [i]) , en utilisant index k .
4.2. Ignorer les éléments b [k] où s [b [k]] intersecte avec s [b [i]] . L'intersection de deux ensembles avec deux nombres peut être calculée dans O (1).
4.3 si k est l'index un élément où b [i] + b [k] == x et s [b [k]] / code> ne se croisit pas avec s [b [i]] , puis la somme des ensembles s [b [k]] et s [b [i]] sont les quatre chiffres recherchés.
performance est:
O (n ^ 2 + n ^ 2 * journal (n ^ 2) + n ^ 2 * journal (n ^ 2)) = O (n ^ 2 * journal (n ^ 2)) = O (n ^ 2 * journal (n))
sur l'étape quatre, lorsque nous iTerons sur les multiples éléments correspondants de B à l'aide de la boucle imbriquée. Pourtant, le nombre total d'itérations des deux boucles imbriquées est limitée par le | b | qui est O (n ^ 2). La recherche rapide n'est pas la variation habituelle, mais celle qui trouve l'élément correspondant à l'indice le plus bas. (Sinon, on peut utiliser l'habituel bsearch et car nous aurions peut-être atterri au milieu, utilisez deux boucles adjacentes, vérifiant des éléments dans les deux directions.)
journal (n ^ 2) est 2log (n) , vous ne dépassez donc pas la complexité temporelle. Cela ne tiendra ce que cela ne tiendra pas compte des éléments en double. Des contrôles supplémentaires seront nécessaires pour cela, mais cela est possible. Par exemple, étant donné le tableau [1, 2, 3] et les sommets [1 + 2, 1 + 3, 2 + 3] , une somme souhaitée de 9 peut être trouvé avec 4 + 5 , mais nous comptons 3 deux fois alors.
@Anurag: OMG. J'ai dû répéter les maths.
Pouvez-vous détailler la 4ème étape? Comment gagnez-vous exactement avec des doublons et un sous-dénombrement?
Comment vérifiez-vous s'ils ont une intersection ou non? (Par exemple, comment vérifier s [b [k]] ne se croisit pas avec S [B [I]]?)
Comme quelques autres affiches, cela peut être fait avec un hachage dans O (n ^ 2)
Cela répond aux exigences, donc +1, mais ce n'est pas O (n ^ 2) comme vous le dites. Un multimap C ++ ne vous donne pas d'insertions et de recherches de temps constants, ce sont logarithmiques.
@IVLAD Mais je suppose que je suppose que le modifier à un Unorded_multimap aurait résoudre le problème.
1) Créez un tableau de toutes les sommes possibles SUMS [O (N ^ 2)]
2) Trier ce tableau dans l'ordre croissant [O (N ^ 2 * LOGN)]
3) Maintenant, ce problème se réduit à la recherche de 2 numéros dans une matrice triée qui somme à un nombre donné X, en temps linéaire. Utilisez 2 pointeurs: un pointeur bas à partir de la valeur la plus basse et un pointeur élevé à partir de la valeur la plus élevée. Si la somme est trop basse, avancez faible. Si la somme est trop élevée, avancez haut (en arrière). Finalement, ils trouveront cette paire ou se croisent (cela peut être facilement prouvé). Ce processus prend du temps linéaire de la taille de la matrice, c'est-à-dire (n ^ 2)
Ceci donne un temps total de O (n ^ 2 * journal n) au besoin.
- Edit -
En fait, ma réponse est très similaire à la réponse de Digmy00001, à l'exception de la recherche finale, où j'utilise une méthode plus rapide (bien que la complexité globale soit la même ...)
+1 belle solution. Mais un problème ici: Supposons que vous recherchez somme = 18 . Et a = {2,3,4,5,7,9,10} maintenant a [0] + a [1] = 5 et A [ 2] + a [5] = 13 , donc a [0] + a [1] + a [2] + a [5] = 18 . Mais a [1] + a [2] = 7 et a [0] + a [5] = 11 d'où a [0] + a [1] + a ] + a [2] + a [5] = 18 . Donc, votre solution imprimera ces deux au lieu de 1. Alors, comment allez-vous aborder le problème. Merci.
@Ecteur: l'algorithme n'est pas nécessaire d'imprimer un ensemble spécifique de quatre; Tous quatre nombres distincts ayant la somme requise sont ok. Le problème avec ma solution est unicité. Il peut inclure un numéro de tableau deux fois. Cela peut également être résolu en stockant également les paires de la carte, puis acceptez une correspondance entre deux paires uniquement si elles n'ont aucune valeur commune.
Vrai. Merci pour votre confirmation. Je déboguais votre solution aujourd'hui et je l'ai trouvée, alors je voulais confirmer à partir de l'auteur. Merci.
Comment trouvez-vous que "deux paires n'ont aucune valeur commune"?
@HengameH: Pour chaque somme dans la matrice SUMS, vous pouvez également stocker les indices des 2 valeurs de la matrice d'origine. À l'étape 3, pour éviter de trouver de fausses combinaisons, vérifiez que les 2 indices de faible n'ont aucune valeur commune avec les 2 indices de haut. Si vous avez des valeurs répétées sur des valeurs répétées faibles et L à des fins élevées et que toutes les combinaisons donnent la bonne somme X, vérifiez simplement toutes les combinaisons. La surcharge d'exécution de cette croix vérifie une fois ou plus est au plus (N ^ 2), elle ne change donc pas la complexité globale.
Trouver quatre éléments dans la matrice dont la somme égale à un nombre donné x
Pour moi après les travaux d'algorithme:
Dim Amt(1 To 10) As Long
Dim i
For i = 1 To 10
Amt(i) = Val(List1.List(i))
Next i
Dim Tot As Integer
Dim lenth As Integer
lenth = List1.ListCount
'sum of 4 numbers
For i = 1 To lenth
For j = 1 To lenth
For k = 1 To lenth
For l = 1 To lenth
If i <> j And i <> k And i <> l And j <> k And j <> l And k <> l Then
Debug.Print CBAmt(i) & " , " & CBAmt(j) & " , " & CBAmt(k) & " , " & CBAmt(l)
If CBAmt(i) + CBAmt(j) + CBAmt(k) + CBAmt(l) = Val(Text1) Then
MsgBox "Found"
found = True
Exit For
End If
End If
Next
If found = True Then Exit For
Next
If found = True Then Exit For
Next
If found = True Then Exit For
Next
C'est une solution O (n ^ 4)!
une solution de java de travail de l'algo. fourni par Nikita Rybak ci-dessus ..
// find four numbers in an array such that they equals to X
class Pair{
int i;
int j;
Pair(int x,int y){
i=x;
j=y;
}
}
public class FindNumbersEqualsSum {
public static void main(String[] args) {
int num[]={1,2,3,4,12,43,32,53,8,-10,4};
get4Numbers(num, 17);
get4Numbers(num, 55);
}
public static void get4Numbers(int a[],int sum){
int len=a.length;
Map<Integer, Pair> sums = new HashMap<Integer, Pair>();
for (int i = 0; i < len; ++i) {
// 'sums' hastable holds all possible sums a[k] + a[l]
// where k and l are both less than i
for (int j = i + 1; j < len; ++j) {
int current = a[i] + a[j];
int rest = sum - current;
// Now we need to find if there're different numbers k and l
// such that a[k] + a[l] == rest and k < i and l < i
// but we have 'sums' hashtable prepared for that
if (sums.containsKey(rest)) {
// found it
Pair p = sums.get(rest);
System.out.println(a[i]+" + "+a[j]+" + "+a[p.i] +" + "+a[p.j]+" = "+sum);
}
}
// now let's put in 'sums' hashtable all possible sums
// a[i] + a[k] where k < i
for (int k = 0; k < i; ++k) {
sums.put(a[i] + a[k],new Pair(i, k));
}
}
}
}
Result:
4 + 8 + 3 + 2 = 17
8 + 4 + 4 + 1 = 17
43 + 8 + 3 + 1 = 55
32 + 8 + 12 + 3 = 55
8 + -10 + 53 + 4 = 55
-10 + 4 + 8 + 53 = 55
Cela ne gère pas vraiment les doublons -
Affiche 53 + 8 + 4 + 3 = 68 et 8 + 4 + 53 + 3 = 68
Pourriez-vous s'il vous plaît expliquer quelle est la "paire de classe" et pourquoi l'utilisez-vous ici?
J'ai écrit une fonction d'exécution O (n ^^ 2) qui n'utilise pas de hashtables mais gère des nombres négatifs et des nombres en double apparemment ok. Je gère des nombres négatifs dans un tableau entier en ajoutant un grand nombre postal (E.g. 100) à tous les entiers de la matrice. Ensuite, je ajuste la cible par cible + = (4 * 100) . Ensuite, lorsque je trouve un résultat, je soustrayez les 100 des entiers du résultat. Voici mon code et des cas de test: laissez-moi savoir si cette complexité de temps O (n ^^ 2).
Désolé, je ne critige pas ce post, mais je vois qu'il y a beaucoup d'améliorations pouvant être apportées. Tout d'abord, essayez de nommer vos variables de manière plus significative afin que ce soit beaucoup plus lisible . Deuxièmement, votre temparray uniquement stocke 1 paire d'indices qui s'ajouteraient à une cible spécifique. Et si vous êtes itération mais que vous avez découvert que cette paire intersectez-vous en quelque sorte avec une autre dans votre boucle finale, mais il y a une autre paire qui ne sera pas? C'est essentiellement pourquoi la réponse "sibshops" utilise une Multi-map .
Ce problème peut être réduit à la recherche de toutes les combinaisons de longueur 4. Pour chaque combinaison ainsi obtenue, sommet les éléments et vérifiez s'il est égal à x.
Quelle est la complexité temporelle de cette solution? Pourriez-vous s'il vous plaît fournir le code?
Ce problème peut être pris comme variation de Pascals Identity,
Voici le code complet: p>
Veuillez excuser comme le code est en Java: P>
10 20 1 60 10 30 40 11 10 60 15 6 20 30 40 1 20 60 5 6 30 40 15 6 11 60 15 5 total combinations : 7
Quelle est la complexité temporelle de cette approche?
Sonne comme des devoirs
On dirait que vous avez besoin d'une méthode de recherche de toutes les permutations de 4 index uniques.
Sont des nombres supérieurs à zéro? Tous les numéros sont-ils uniques?
Toute restriction sur x ou chiffres?
Voulez-vous dire que vous voulez écrire une fonction qui prend un tableau , son
longueur et une valeuret renvoie un ensemble de 4 membres de laarray dont la somme estla valeur ? Voulez-vous qu'il retourne l'ensemble de tous les ensembles possibles de 4 membres dont la somme estvaleur ? Et s'il n'y en a pas trouvé?Ajout de l'étiquette de devoirs car cela fait une heure et rien ne dit que ce n'est pas le cas.
Pour ce que ça vaut la peine, je me souviens de voir le problème avant et d'entendre des personnes ayant des solutions impliquant une sorte de
n ^ 2 (probablement les sommes de chaque paire), puisn ^ 2 Recherches binaires, entraînant la complexité demandée. Je n'ai jamais compris comment ils ont traité certains problèmes de certains indices cependant. Je pensais juste que je partagerais au cas où tout le monde veut poursuivre cette approche.Les chiffres ne sont pas uniques ou positifs, j'ai besoin d'une seule option, pas toutes les permutations de 4 numéros