إيجاد العنصر المكرّر في المصفوفة

المطلوب في هذه المسألة هو إيجاد العنصر المكرّر في مصفوفة تحتوي على مجموعة من العناصر المرتّبة، ويتكرّر فيها عنصر واحد فقط.

مثال:

Input :  arr[] = { 1, 2 , 3 , 4 , 4}
Output :  4

Input :  arr[] = { 1 , 1 , 2 , 3 , 4}
Output :  1

خطوات الخوارزمية

الحل البسيط هو المرور على المصفوفة بأكملها والتحقق من أن العنصر الحالي مكرّر، ثم يُعاد العنصر المكرر إن وجد. يبلغ التعقيد الزمني لهذه الطريقة المقدار O(n)‎.

يمكن تحسين هذه الخوارزمية باعتماد أسلوب فرِّق تسد وذلك بالاستفادة من خوارزمية البحث الثنائي، وفق الخطوات التالية:

1. التحقق من أنّ العنصر الموجود في وسط المصفوفة هو العنصر المكرّر.
2. إن لم يتحقق الشرط السابق، يجري التحقق من وجود العنصر الوسطي في مكانه الصحيح، فإن كان كذلك سيكون العنصر المكرّر إلى يمين العنصر الوسطي.
3. أما إن كان العنصر الوسطي في مكانه الصحيح، فإنّ العنصر المكرّر سيكون إلى يساره.

تنفيذ الخوارزمية

تعرض الأمثلة التالية طريقة تنفيذ الخوارزمية في عدد من لغات البرمجة:

• C++‎:

#include <bits/stdc++.h> 
using namespace std; 

// تعيد الدالة موقع الظهور الثاني للعنصر المكرر
// n-1 تفترض الدالة أنّ عناصر المصفوفة تتدرج ضمن النطاق 1 إلى 
int findRepeatingElement(int arr[], int low, int high) 
{ 
	// low = 0 , high = n-1; 
	if (low > high) 
		return -1; 

	int mid = (low + high) / 2; 

	// التحقق من كون العنصر الوسطي هو العنصر المكرر
	if (arr[mid] != mid + 1) 
	{ 
		if (mid > 0 && arr[mid]==arr[mid-1]) 
			return mid; 

		// إن لم يكن العنصر الوسطي في موقعه الصحيح
		// فهذا يعني أنّ العنصر المكرر سيكون إلى يساره
		return findRepeatingElement(arr, low, mid-1); 
	} 

	// إن كان العنصر الوسطي في موقعه الصحيح
	// فإنّ العنصر المكرّر سيكون إلى يمينه
	return findRepeatingElement(arr, mid+1, high); 
} 

// اختبار الدالة السابقة 
int main() 
{ 
	int arr[] = {1, 2, 3, 3, 4, 5}; 
	int n = sizeof(arr) / sizeof(arr[0]); 
	int index = findRepeatingElement(arr, 0, n-1); 
	if (index != -1) 
		cout << arr[index]; 
	return 0; 
}

• بايثون:

# تعيد الدالة موقع الظهور الثاني للعنصر المكرر
# n-1 تفترض الدالة أنّ عناصر المصفوفة تتدرج ضمن النطاق 1 إلى 
def findRepeatingElement(arr, low, high): 

	# low = 0 , high = n-1 
	if low > high: 
		return -1

	mid = (low + high) / 2

	# التحقق من كون العنصر الوسطي هو العنصر المكرر
	if (arr[mid] != mid + 1): 
	
		if (mid > 0 and arr[mid]==arr[mid-1]): 
			return mid 

		# إن لم يكن العنصر الوسطي في موقعه الصحيح 
		# فهذا يعني أنّ العنصر المكرر سيكون إلى يساره
		return findRepeatingElement(arr, low, mid-1) 

	# إن كان العنصر الوسطي في موقعه الصحيح 
	# فإنّ العنصر المكرّر سيكون إلى يمينه
	return findRepeatingElement(arr, mid+1, high) 

# اختبار الدالة السابقة 
arr = [1, 2, 3, 3, 4, 5] 
n = len(arr) 
index = findRepeatingElement(arr, 0, n-1) 
if (index is not -1): 
	print arr[index] 

#اختبار الدالة السابقة

• جافا:

class Test 
{ 
	// يعيد التابع موقع الظهور الثاني للعنصر المكرر
	//  n-1 تفترض الدالة أنّ عناصر المصفوفة تتدرج ضمن النطاق 1 إلى  
	static int findRepeatingElement(int arr[], int low, int high) 
	{ 
		// low = 0 , high = n-1; 
		if (low > high) 
			return -1; 
	
		int mid = (low + high) / 2; 
	
		// التحقق من كون العنصر الوسطي هو العنصر المكرر 
		if (arr[mid] != mid + 1) 
		{ 
			if (mid > 0 && arr[mid]==arr[mid-1]) 
				return mid; 
	
			// إن لم يكن العنصر الوسطي في موقعه الصحيح 
			// فهذا يعني أنّ العنصر المكرر سيكون إلى يساره 
			return findRepeatingElement(arr, low, mid-1); 
		} 
	
		// إن كان العنصر الوسطي في موقعه الصحيح 
		// فإنّ العنصر المكرّر سيكون إلى يمينه
		return findRepeatingElement(arr, mid+1, high); 
	} 
	
	// اختبار التابع السابق
	public static void main(String[] args) 
	{ 
		int arr[] = {1, 2, 3, 3, 4, 5}; 
		int index = findRepeatingElement(arr, 0, arr.length-1); 
		if (index != -1) 
			System.out.println(arr[index]); 
	} 
}

تعطي الشيفرات السابقة المخرجات التالية:

3

التعقيد الزمني

يبلغ التعقيد الزمني لهذه الخوارزمية المقدار ‎O(log n)‎.

مصادر

• صفحة Find the only repeating element in a sorted array of size n في توثيق الخوارزميات في موقع GeeksforGeeks.