Algorithms/majority element

العنصر الغالب Majority Element هو العنصر الذي يظهر أكثر من n/2 مرة في مصفوفة مرتبة تحتوي على n من الأعداد الصحيحة.

مثال:

Input: arr[] = {1, 2, 3, 3, 3, 3, 10}, x = 3
Output: True (x appears more than n/2 times in the given array)

Input: arr[] = {1, 1, 2, 4, 4, 4, 6, 6}, x = 4
Output: False (x doesn't appear more than n/2 times in the given array)

Input: arr[] = {1, 1, 1, 2, 2}, x = 1
Output: True (x appears more than n/2 times in the given array)

الطريقة الأولى: البحث الخطي

يمكن إيجاد العنصر الغالب في مصفوفة مرتبة بإجراء بحث خطي عن أول ظهور للعنصر، وعند العثور عليه (في الموقع i على سبيل الفرض) تتحقّق الخوارزمية من العنصر الموجود في الموقع i + n/2، فإن كان العنصر نفسه موجودًا في ذلك الموقع، تعيد الخوارزمية القيمة 1 وإلا أعادت القيمة 0.

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

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

• C++‎:

# include <stdio.h> 
# include <stdbool.h> 

bool isMajority(int arr[], int n, int x) 
{ 
	int i; 

	/* n الحصول على آخر موقع بالنسبة إلى 
	(زوجي أو فردي) */
	int last_index = n%2? (n/2+1): (n/2); 

	/* البحث عن أول ظهور للعنصر المعطى في المصفوفة */
	for (i = 0; i < last_index; i++) 
	{ 
		/* n/2 إن كان العنصر المعطى موجودًا وكانت عدد مرات تكراره */
		if (arr[i] == x && arr[i+n/2] == x) 
			return 1; 
	} 
	return 0; 
} 

/* اختبار الدالة السابقة */
int main() 
{ 
	int arr[] ={1, 2, 3, 4, 4, 4, 4}; 
	int n = sizeof(arr)/sizeof(arr[0]); 
	int x = 4; 
	if (isMajority(arr, n, x)) 
		printf("%d appears more than %d times in arr[]", 
			x, n/2); 
	else
		printf("%d does not appear more than %d times in arr[]", 
				x, n/2); 

return 0; 
}

• بايثون:

def isMajority(arr, n, x): 
	#  n الحصول على آخر موقع بالنسبة إلى 
	(زوجي أو فردي)
	last_index = (n//2 + 1) if n % 2 == 0 else (n//2) 

	# البحث عن أول ظهور للعنصر المعطى في المصفوفة 
	for i in range(last_index): 
		# n/2 إن كان العنصر المعطى موجودًا وكانت عدد مرات تكراره 
		if arr[i] == x and arr[i + n//2] == x: 
			return 1

# اختبار الدالة السابقة 
arr = [1, 2, 3, 4, 4, 4, 4] 
n = len(arr) 
x = 4
if (isMajority(arr, n, x)): 
	print ("% d appears more than % d times in arr[]"
											%(x, n//2)) 
else: 
	print ("% d does not appear more than % d times in arr[]"
													%(x, n//2))

• جافا:

import java.io.*; 

class Majority { 

	static boolean isMajority(int arr[], int n, int x) 
	{ 
		int i, last_index = 0; 

		/*  n الحصول على آخر موقع بالنسبة إلى 
	(زوجي أو فردي) */
		last_index = (n%2==0)? n/2: n/2+1; 

		/* البحث عن أول ظهور للعنصر المعطى في المصفوفة */
		for (i = 0; i < last_index; i++) 
		{ 
			/* n/2 إن كان العنصر المعطى موجودًا وكانت عدد مرات تكراره */
			if (arr[i] == x && arr[i+n/2] == x) 
				return true; 
		} 
		return false; 
	} 

	/* اختبار التابع السابق */
	public static void main (String[] args) { 
		int arr[] = {1, 2, 3, 4, 4, 4, 4}; 
		int n = arr.length; 
		int x = 4; 
		if (isMajority(arr, n, x)==true) 
		System.out.println(x+" appears more than "+ 
							n/2+" times in arr[]"); 
		else
		System.out.println(x+" does not appear more than "+ 
							n/2+" times in arr[]"); 
	} 
}

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

4 appears more than 3 times in arr[]

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

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

الطريقة الثانية: البحث الثنائي

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

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

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

• C++‎:

# include <stdio.h> 
# include <stdbool.h> 


/* arr[low..high] إن كان العنصر المعطى موجودًا في المصفوفة
تعيد الدالة موقع أول ظهور لذلك العنصر، وإلا تعيد القيمة 1- */
int _binarySearch(int arr[], int low, int high, int x); 

/* n/2 تعيد الدالة قيمة صحيحة إن كان عدد مرات تكرار العنصر المعطى
n في المصفوفة المعطاة ذات الحجم */
bool isMajority(int arr[], int n, int x) 
{ 
	/* البحث عن موقع أول ظهور للعنصر المعطى في المصفوفة */
	int i = _binarySearch(arr, 0, n-1, x); 

	/* تعيد الدالة قيمة خاطئة إن لم يكن العنصر موجودًا */
	if (i == -1) 
		return false; 

	/* n/2 التحقق من أن عدد مرات تكرار العنصر هي أكثر من */
	if (((i + n/2) <= (n -1)) && arr[i + n/2] == x) 
		return true; 
	else
		return false; 
} 

/* arr[low..high] إن كان العنصر المعطى موجودًا في المصفوفة
تعيد الدالة موقع أول ظهور لذلك العنصر، وإلا تعيد القيمة 1- */
int _binarySearch(int arr[], int low, int high, int x) 
{ 
	if (high >= low) 
	{ 
		int mid = (low + high)/2; /*low + (high - low)/2;*/

		/* arr[mid] التحقّق من أنّ العنصر
		هو أول ظهور للعنصر المعطى، وذلك بتحقق أحد الشرطين التاليين:
		(1) mid == 0 و arr[mid] == x
		(2) arr[mid-1] < x و arr[mid] == x
		*/
		if ( (mid == 0 || x > arr[mid-1]) && (arr[mid] == x) ) 
			return mid; 
		else if (x > arr[mid]) 
			return _binarySearch(arr, (mid + 1), high, x); 
		else
			return _binarySearch(arr, low, (mid -1), x); 
	} 

	return -1; 
} 

/* اختبار الدوال السابقة */
int main() 
{ 
	int arr[] = {1, 2, 3, 3, 3, 3, 10}; 
	int n = sizeof(arr)/sizeof(arr[0]); 
	int x = 3; 
	if (isMajority(arr, n, x)) 
		printf("%d appears more than %d times in arr[]", 
			x, n/2); 
	else
		printf("%d does not appear more than %d times in arr[]", 
			x, n/2); 
	return 0; 
}

• بايثون:

# arr[low..high] إن كان العنصر المعطى موجودًا في المصفوفة
# تعيد الدالة موقع أول ظهور لذلك العنصر، وإلا تعيد القيمة 1-
def isMajority(arr, n, x): 
	
	# البحث عن موقع أول ظهور للعنصر المعطى في المصفوفة 
	i = _binarySearch(arr, 0, n-1, x) 

	# إن لم يكن العنصر موجودًا تعيد الدالة قيمة خاطئة
	if i == -1: 
		return False

	# n/2 التحقق من أن عدد مرات تكرار العنصر هي أكثر من */ 
	if ((i + n//2) <= (n -1)) and arr[i + n//2] == x: 
		return True
	else: 
		return False

# arr[low..high] إن كان العنصر المعطى موجودًا في المصفوفة
# تعيد الدالة موقع أول ظهور لذلك العنصر، وإلا تعيد القيمة 1- 
def _binarySearch(arr, low, high, x): 
	if high >= low: 
		mid = (low + high)/2 # low + (high - low)/2; 

		'''  arr[mid] التحقّق من أنّ العنصر 
			هو أول ظهور للعنصر المعطى، وذلك بتحقق أحد الشرطين التاليين:
			(1) mid == 0 و arr[mid] == x 
			(2) arr[mid-1] < x و arr[mid] == x'''
		
		if (mid == 0 or x > arr[mid-1]) and (arr[mid] == x): 
			return mid 
		elif x > arr[mid]: 
			return _binarySearch(arr, (mid + 1), high, x) 
		else: 
			return _binarySearch(arr, low, (mid -1), x) 
	return -1


# اختبار الدوال السابقة 
arr = [1, 2, 3, 3, 3, 3, 10] 
n = len(arr) 
x = 3
if (isMajority(arr, n, x)): 
	print ("% d appears more than % d times in arr[]"
											% (x, n//2)) 
else: 
	print ("% d does not appear more than % d times in arr[]"
													% (x, n//2))

• جافا:

import java.io.*; 

class Majority { 

	/* arr[low..high] إن كان العنصر المعطى موجودًا في المصفوفة
		تعيد الدالة موقع أول ظهور لذلك العنصر، وإلا تعيد القيمة 1- */
	static int _binarySearch(int arr[], int low, int high, int x) 
	{ 
		if (high >= low) 
		{ 
			int mid = (low + high)/2; /*low + (high - low)/2;*/

			/* arr[mid] التحقّق من أنّ العنصر 
				هو أول ظهور للعنصر المعطى، وذلك بتحقق أحد الشرطين التاليين:
				(1) mid == 0 و arr[mid] == x 
				(2) arr[mid-1] < x و arr[mid] == x
			*/
			if ( (mid == 0 || x > arr[mid-1]) && (arr[mid] == x) ) 
				return mid; 
			else if (x > arr[mid]) 
				return _binarySearch(arr, (mid + 1), high, x); 
			else
				return _binarySearch(arr, low, (mid -1), x); 
		} 

		return -1; 
	} 


	/* n/2 تعيد الدالة قيمة صحيحة إن كان عدد مرات تكرار العنصر المعطى 
		n في المصفوفة المعطاة ذات الحجم */
	static boolean isMajority(int arr[], int n, int x) 
	{ 
		/* البحث عن موقع أول ظهور للعنصر المعطى في المصفوفة */
		int i = _binarySearch(arr, 0, n-1, x); 

		/* تعيد الدالة قيمة خاطئة إن لم يكن العنصر موجودًا */
		if (i == -1) 
			return false; 

		/* n/2 التحقق من أن عدد مرات تكرار العنصر هي أكثر من */
		if (((i + n/2) <= (n -1)) && arr[i + n/2] == x) 
			return true; 
		else
			return false; 
	} 

	/* اختبار الدوال السابقة */
	public static void main (String[] args) { 

		int arr[] = {1, 2, 3, 3, 3, 3, 10}; 
		int n = arr.length; 
		int x = 3; 
		if (isMajority(arr, n, x)==true) 
			System.out.println(x + " appears more than "+ 
							n/2 + " times in arr[]"); 
		else
			System.out.println(x + " does not appear more than " + 
							n/2 + " times in arr[]"); 
	} 
}

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

3 appears more than 3 times in arr[]

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

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

مصادر

• صفحة Check for Majority Element in a sorted array في توثيق الخوارزميات في موقع GeeksforGeeks.