donnée n matrices avec Tailleof N, et ils sont tous triés, s'il ne vous permet pas d'utiliser un espace supplémentaire, comment trouver leurs données communes efficacement ou avec une complexité moins de temps?
pour ex: p>
not_found_flag = false
for each element 'v' in row-1
for each row 'i' in the remaining set
perform binary search for 'v' in 'i'
if 'v' not found in row 'i'
not_found_flag = true
break
if not not_found_flag
print element 'v' as it is one of the common element
5 Réponses :
Il semble que cela puisse être fait dans Appelons les tableaux < Code> a_1 via Explication de l'algorithme. Nous utilisons le premier tableau (ou tout tableau arbitraire) comme algorithme de référence et itérer à travers tous les autres tableaux en parallèle (type d'étape de fusion d'une tresse de fusion, sauf avec n matrices.) Chaque valeur de la référence.) Le tableau qui est commun à tous les tableaux doit être présent dans tous les autres tableaux. Donc, pour chaque autre tableau (puisqu'ils sont triés), nous augmentons l'index À la fin, nous avons imprimé toutes les valeurs communes à tous les tableaux, tout en ayant examiné chaque élément une fois. < / p> Mise en œuvre Java (pour la brièveté, Sans le hack supplémentaire), en utilisant votre exemple d'entrée: sortie: O (n ^ 2) ; C'est-à-dire, je regarde juste chaque élément une fois. Notez que si un élément est commun à tous les tableaux, il doit exister dans l'un d'eux. Aussi à des fins d'illustration (et puisque vous avez utilisé la boucle pour la boucle supérieure), je suppose que nous pouvons garder un index pour chacun des tableaux, mais je vais parler de la manière de se déplacer plus tard. a_n et utilisez indices à partir de 1. pseudocode: x_i jusqu'à la valeur de cet index a_i [x_i] est au moins la valeur que nous recherchons (Nous ne nous soucions pas des valeurs moindre; ils ne peuvent pas être courants.) Nous pouvons le faire car les matrices sont triées et donc de la nondréquine monotone. Si tous les tableaux avaient cette valeur, nous l'imprimez, sinon nous incrempreons x_1 dans le tableau de référence et continue de continuer. Nous devons le faire même si nous n'imprimons pas la valeur. A_1 . S'ils sont tous identiques, imprimez cette valeur, puis stockez les indices x_2 ... x_n comme premier élément de chaque tableau lui-même.
une version O (n ^ 2) (Python) qui n'utilise pas de stockage supplémentaire, mais modifie le tableau d'origine. Permet de stocker les éléments communs sans les imprimer:
data = [
[10, 160, 200, 500, 500],
[4, 150, 160, 170, 500],
[2, 160, 200, 202, 203],
[3, 150, 155, 160, 300],
[3, 150, 155, 160, 301],
]
for k in xrange(len(data)-1):
A, B = data[k], data[k+1]
i, j, x = 0, 0, None
while i<len(A) or j<len(B):
while i<len(A) and (j>=len(B) or A[i] < B[j]):
A[i] = x
i += 1
while j<len(B) and (i>=len(A) or B[j] < A[i]):
B[j] = x
j += 1
if i<len(A) and j<len(B):
x = A[i]
i += 1
j += 1
print data[-1]
Ceci est une solution en Python O (n ^ 2) code>, n'utilise aucun espace supplémentaire mais détruit les listes: def find_common(lists):
num_lists = len(lists)
first_list = lists[0]
for j in first_list[::-1]:
common_found = True
for i in range(1,num_lists):
curr_list = lists[i]
while curr_list[len(curr_list)-1] > j:
curr_list.pop()
if curr_list[len(curr_list)-1] != j:
common_found = False
break
if common_found:
return j
Voici l'implémentation Java
@Test
public void commonElementsInNSortedArrayTest() {
int arr[][] = { {1, 5, 10, 20, 40, 80},
{6, 7, 20, 80, 100},
{3, 4, 15, 20, 30, 70, 80, 120}
};
Integer result[] = ArrayUtils.commonElementsInNSortedArrays(arr);
assertThat(result, equalTo(new Integer[]{20, 80}));
arr = new int[][]{
{23, 34, 67, 89, 123, 566, 1000},
{11, 22, 23, 24,33, 37, 185, 566, 987, 1223, 1234},
{23, 43, 67, 98, 566, 678},
{1, 4, 5, 23, 34, 76, 87, 132, 566, 665},
{1, 2, 3, 23, 24, 344, 566}
};
result = ArrayUtils.commonElementsInNSortedArrays(arr);
assertThat(result, equalTo(new Integer[]{23, 566}));
}
Cette solution SWIFT fait une copie de l'original mais pourrait être modifiée pour prendre un paramètre inout de sorte qu'il ne prend aucun espace supplémentaire. Je l'ai laissé une copie parce que je pense qu'il est préférable de ne pas modifier l'original puisqu'il supprime des éléments. Il est possible de ne pas éliminer les éléments en gardant des indices, mais cet algorithme supprime des éléments à suivre l'endroit où il se trouve. Ceci est une approche fonctionnelle et peut ne pas être super efficace mais fonctionne. Comme il est fonctionnel moins de logique conditionnel est nécessaire. Je l'ai posté parce que je pensais que cela pourrait être une approche différente qui pourrait être intéressante pour les autres, et d'autres peuvent peut-être trouver des moyens de la rendre plus efficace.
Vous avez besoin d'un espace supplémentaire pour stocker les éléments communs (possibles) ...
@Mitchwheat. S'il vous plaît regarder le pseudo code ci-dessus. Si nous sommes bons avec simplement imprimer les éléments communs, avons-nous vraiment besoin de stockage supplémentaire?
Êtes-vous vraiment sauvegarde de toute chose par la recherche binaire .. Depuis que vous devez trouver tous les éléments communs, pourquoi ne faites-vous pas simplement numériser le tableau de tri et être fait dans O (n)
@smk. Il existe des tableaux différents et chacun d'eux est trié de manière indépendante. J'ai édité la question avec l'exemple. Nous ne pouvons pas trouver des éléments communs dans O (n) en numérisant les tableaux 'n'. Cela ressemble plus à une matrice carrée NXN où chaque rangée est triée individuellement.