Artan sırada verilmiş üç dizi içerisinde bulunan ortak elemanı bulmamıza yarayan algoritmaya bakacağız.
Örneğin
ar1[] = {1, 5, 10, 20, 40, 80}
ar2[] = {6, 7, 20, 80, 100}
ar3[] = {3, 4, 15, 20, 30, 70, 80, 120}
Output: 20, 80
ar1[] = {1, 5, 5}
ar2[] = {3, 4, 5, 5, 10}
ar3[] = {5, 5, 10, 20}
Output: 5, 5
Basit olarak ilk çözüm link! algoritmasını uygulamak ve elde edilen değerleri yedek bir dizi içerisinde tutmaktır. Bu çözüm ile karmaşıklık O(n1+n2+n3) olacaktır.
Yukarıda ki çözüm ekstra olarak hafıza ve iki adet döngü içermektedir. Oysa bu soruyu tek bir döngüde ve ektra hafıza gerektirmeden çözebiliriz.
Çözüm aşağıdaki gibidir.
def find_common(ar1, ar2, ar3):
i, j, k = 0, 0, 0
n1, n2, n3 = len(ar1), len(ar2), len(ar3)
while i < n1 and j < n2 and k < n3:
if ar1[i] == ar2[j] and ar2[j] == ar3[k]:
print(ar1[i])
i, j, k = i + 1, j + 1, k + 1
elif ar1[i] < ar2[j]:
i += 1
elif ar2[j] < ar3[k]:
j += 1
else:
k += 1
if __name__ == '__main__':
ar1 = [1, 5, 10, 20, 40, 80]
ar2 = [6, 7, 20, 80, 100]
ar3 = [3, 4, 15, 20, 30, 70, 80, 120]
find_common(ar1, ar2, ar3)
Karmaşıklık O(n1+n2+n3) olacaktır.
Comments
comments powered by Disqus