तीन सॉर्टेड सरणियों में सामान्य तत्व खोजने के लिए हम थ्री-पॉइंटर तकनीक का उपयोग करते हैं। चूंकि सरणियां सॉर्टेड हैं, हम एक ही पास में सभी तीनों को पार कर सकते हैं।
एल्गोरिदम
- तीन पॉइंटर्स
i, j, kको 0 पर आरंभ करें (प्रत्येक सरणी के लिए एक)। - जब तक सभी पॉइंटर्स अपनी सरणी की सीमा के भीतर हैं:
- यदि
arr1[i] == arr2[j] == arr3[k]→ सामान्य तत्व मिला, प्रिंट करें और तीनों पॉइंटर्स बढ़ाएं। - अन्यथा, सबसे छोटे मान वाले पॉइंटर को बढ़ाएं।
- यदि
उदाहरण
using System;
class Demo {
static void CommonElements(int[] one, int[] two, int[] three) {
int i = 0, j = 0, k = 0;
while (i < one.Length && j < two.Length && k < three.Length) {
if (one[i] == two[j] && two[j] == three[k]) {
Console.Write(one[i] + " ");
i++; j++; k++;
}
else if (one[i] < two[j])
i++;
else if (two[j] < three[k])
j++;
else
k++;
}
}
public static void Main() {
int[] one = { 20, 35, 57, 70 };
int[] two = { 9, 35, 57, 70, 92 };
int[] three = { 25, 35, 55, 57, 67, 70 };
Console.Write("Common elements: ");
CommonElements(one, two, three);
}
}
आउटपुट
Common elements: 35 57 70
चरण-दर-चरण ट्रेस
| चरण | i (one) | j (two) | k (three) | क्रिया |
|---|---|---|---|---|
| 1 | 20 | 9 | 25 | 9 सबसे छोटा → j++ |
| 2 | 20 | 35 | 25 | 20 सबसे छोटा → i++ |
| 3 | 35 | 35 | 25 | 25 सबसे छोटा → k++ |
| 4 | 35 | 35 | 35 | सभी बराबर → प्रिंट 35, i++, j++, k++ |
| ... | ... | ... | ... | इसी तरह 57 और 70 मिलते हैं |
जटिलता
- समय: O(n1 + n2 + n3) - रैखिक समय
- स्थान: O(1) - केवल पॉइंटर्स
डुप्लिकेट हैंडलिंग
यदि सरणियों में डुप्लिकेट हैं और आप प्रत्येक सामान्य तत्व को केवल एक बार चाहते हैं:
if (one[i] == two[j] && two[j] == three[k]) {
Console.Write(one[i] + " ");
int val = one[i];
while (i < one.Length && one[i] == val) i++;
while (j < two.Length && two[j] == val) j++;
while (k < three.Length && three[k] == val) k++;
}