إيجاد العنصر الغالب في مصفوفة مرتبة
العنصر الغالب 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.