إيجاد العنصر الغالب في مصفوفة مرتبة
اذهب إلى التنقل
اذهب إلى البحث
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.
العنصر الغالب 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.