العثور على العنصر الفريد في المصفوفة
تعثر هذه الخوارزمية على العنصر الفريد في مصفوفة تضمّ عناصر تتكرر ثلاث مرّات.
مثال:
Input: arr[] = {12, 1, 12, 3, 12, 1, 1, 2, 3, 3}
Output: 2
تتكرّر جميع العناصر في المصفوفة المعطاة ثلاث مرّات باستثناء العدد 2 الذي يظهر مرّة واحدة فقط.
الطريقة الأولى
هناك عدة طرق للكشف عن العنصر الفريد في المصفوفة، فمثلًا يمكن استخدام عمليات الترتيب وبتعقيد زمني قدره O(nLogn)، ويمكن استخدام التقطيع hashing وبتعقيد زمني قدره O(n) مع الحاجة إلى مساحة إضافية في الذاكرة.
ولكن يمكن استخدام العوامل الخاصة بالبتات لحلّ هذه المسألة بتعقيد زمني قدره O(n) دون استهلاك الكثير من المساحة.
خطوات الخوارزمية
تتبع الخوارزمية الخطوات التالية:
- تستخدم الخوارزمية حلقة تكرارية للمرور على جميع عناصر المصفوفة، وفي نهاية كل دورة تسجّل قيمتين هما:
- الواحدات: البتات التي تظهر للمرة الأولى أو الرابعة أو السابعة ... الخ.
- الاثنينات: البتات التي تظهر للمرة الثانية أو الخامسة أو الثامنة ... الخ.
- تعيد الخوارزمية قيمة الواحدات.
تبدأ الواحدات والاثنينات بقيمة 0 في بداية عمل الحلقة التكرارية، ثم نبحث عن البتات المعيّنة والمشتركة بين العنصر الجديد والقيمة السابقة للواحدات، وهذه البتات المشتركة المعيّنة هي البتات التي يجب إضافة إلى الاثنينات؛ ولهذا يطبق العامل OR على البتات المعيّنة مع الاثنينات. كذلك تحصل الاثنينات على بعض البتات الإضافية والتي تظهر للمرة الثالثة، وستحذف هذه البتات الزائدة فيما بعد.
تحدث الواحدات بتطبيق العامل XOR على العنصر الجديد مع القمية السابقة للواحدات، وقد تكون بعض البتات التي تظهر للمرة الثالثة، وستحذف هذه البتات أيضًا فيما بعد.
تحتوي الواحدات والاثنينات على البتات الزائدة التي تظهر للمرة الثالثة، لذا تحذف هذه البتات عن طريق إيجاد البتات المعيّنة والمشتركة بين الواحدات والاثنينات.
تنفيذ الخوارزمية
تعرض الأمثلة التالية طريقة تنفيذ الخوارزمية في عدد من لغات البرمجة:
- C++:
#include <bits/stdc++.h>
using namespace std;
int getSingle(int arr[], int n)
{
int ones = 0, twos = 0 ;
int common_bit_mask;
// لنأخذ المثال التالي لفهم الخوارزمية
// {3, 3, 2, 3}
for( int i=0; i< n; i++ )
{
/* "one & arr[i]"يعطي التعبير
البتات الموجودة في الواحدات وفي العنصر الجديد من المصفوفة
OR تضاف هذه البتات إلى الاثنينات باستخدام العامل
تصبح قيم الاثنينات بعد الدورة الأولى والثاني والثالثة والرابعة
0, 3, ,3, 1 */
twos = twos | (ones & arr[i]);
/* تطبيق العامل XOR على البتات الجديد مع القيمة السابقة للواحدات
للحصول على جميع البتات التي تظهر لعددٍ فردي من المرات
تصبح قيم الواحدات بعد الدورة الأولى والثاني والثالثة والرابعة
3, 2, ,0, 3*/
ones = ones ^ arr[i];
/* البتات المشتركة هي البتات التي تظهر للمرة الثالثة
لذا يجب أن لا تكون هذه البتات موجودة في الواحدات والاثنينات
يحتوي هذا المتغير على جميع تلك البتات كأصفار، وذلك ليكون بالإمكان
حذف هذه البتات من الواحدات والاثنينات
تصبح قيمة المتغير في الدورة الأولى والثاني والثالثة والرابعة
00, 00, 01, 10
*/
common_bit_mask = ~(ones & twos);
/* حذف البتات المشتركة (البتات التي تظهر للمرة الثالثة) من الواحدات
تصبح قيمة الواحدات في الدورة الأولى والثاني والثالثة والرابعة
3, 0, 0, 2
*/
ones &= common_bit_mask;
/* حذف البتات المشتركة (البتات التي تظهر للمرة الثالثة) من الاثنينات
تصبح قيمة الواحدات في الدورة الأولى والثاني والثالثة والرابعة
0, 3, 1, 0 */
twos &= common_bit_mask;
}
return ones;
}
// اختبار الدالة السابقة
int main()
{
int arr[] = {3, 3, 2, 3};
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"The element with single occurrence is "<<getSingle(arr, n);
return 0;
}
- بايثون:
def getSingle(arr, n):
ones = 0
twos = 0
for i in range(n):
# "twos & arr[i]"يعطي التعبير
# البتات الموجودة في الاثنينات وفي العنصر الجديد من المصفوفة
# OR تضاف هذه البتات إلى الاثنينات باستخدام العامل
twos = twos | (ones & arr[i])
# "one & arr[i]"يعطي التعبير
# البتات الموجودة في الواحدات وفي العنصر الجديد من المصفوفة
# OR تضاف هذه البتات إلى الواحدات باستخدام العامل
ones = ones ^ arr[i]
# البتات المشتركة هي البتات التي تظهر للمرة الثالثة
# لذا يجب أن لا تكون هذه البتات موجودة في الواحدات والاثنينات
# يحتوي هذا المتغير على جميع تلك البتات كأصفار، وذلك ليكون بالإمكان
# حذف هذه البتات من الواحدات والاثنينات
common_bit_mask = ~(ones & twos)
# حذف البتات المشتركة (البتات التي تظهر للمرة الثالثة) من الواحدات
ones &= common_bit_mask
# حذف البتات المشتركة (البتات التي تظهر للمرة الثالثة) من الاثنينات
twos &= common_bit_mask
return ones
# اختبار الدالة السابقة
arr = [3, 3, 2, 3]
n = len(arr)
print("The element with single occurrence is ",
getSingle(arr, n))
- جافا:
class GFG
{
static int getSingle(int arr[], int n)
{
int ones = 0, twos = 0;
int common_bit_mask;
for(int i=0; i<n; i++ )
{
/*"twos & arr[i]"يعطي التعبير
# البتات الموجودة في الاثنينات وفي العنصر الجديد من المصفوفة
OR تضاف هذه البتات إلى الاثنينات باستخدام العامل */
twos = twos | (ones & arr[i]);
/*"ones & arr[i]"يعطي التعبير
# البتات الموجودة في الواحدات وفي العنصر الجديد من المصفوفة
OR تضاف هذه البتات إلى الواحدات باستخدام العامل */
ones = ones ^ arr[i];
/* البتات المشتركة هي البتات التي تظهر للمرة الثالثة
لذا يجب أن لا تكون هذه البتات موجودة في الواحدات والاثنينات
يحتوي هذا المتغير على جميع تلك البتات كأصفار، وذلك ليكون بالإمكان
حذف هذه البتات من الواحدات والاثنينات */
common_bit_mask = ~(ones & twos);
/* حذف البتات المشتركة (البتات التي تظهر للمرة الثالثة) من الواحدات */
ones &= common_bit_mask;
/* حذف البتات المشتركة (البتات التي تظهر للمرة الثالثة) من الاثنينات */
twos &= common_bit_mask;
}
return ones;
}
// اختبار التابع السابق
public static void main(String args[])
{
int arr[] = {3, 3, 2, 3};
int n = arr.length;
System.out.println("The element with single occurrence is " + getSingle(arr, n));
}
}
تعطي الشيفرات السابقة المخرجات التالية:
The element with single occurrence is 2
التعقيد الزمني
يبلغ التعقيد الزمني لهذه الطريقة المقدار O(n)، وتستهلك مساحة قدرها O(1) من الذاكرة.
الطريقة الثانية
يمكن جمع البتات الموجودة في نفس الموقع لجميع الأرقام ثم أخذ باقي القسمة على 3، وبهذا تكون البتات الفريدة هي البتات التي لا يكون مجموعها من مضاعفات العدد 3.
مثال:
التمثيل الثنائي للمصفوفة {5, 5, 5, 8} هو 101, 101, 101, 1000.
باقي قسمة مجموع البتات الأولى (جهة اليمين) في كل عدد على 3:
(1 + 1 + 1+ 0) % 3 = 0
باقي قسمة مجموع البتات الثانية في كل عدد على 3:
(0 + 0 + 0 + 0)%0 = 0;
باقي قسمة مجموع البتات الثالثة في كل عدد على 3:
(1 + 1 + 1 + 0)%3 = 0;
باقي قسمة مجموع البتات الرابعة في كل عدد على 3:
(1)%3 = 1;
وهذا يعني أنّ العدد الذي يظهر مرة واحدة في المصفوفة هو العدد 1000 أي العدد 8.
تنفيذ الخوارزمية
تعرض الأمثلة التالية طريقة تنفيذ الخوارزمية في عدد من لغات البرمجة:
- C++:
#include <bits/stdc++.h>
using namespace std;
#define INT_SIZE 32
int getSingle(int arr[], int n)
{
// تهيئة النتيجة
int result = 0;
int x, sum;
// المرور على جميع البتات
for (int i = 0; i < INT_SIZE; i++)
{
// حساب مجموع البتات في الدورة الحالية وفي جميع عناصر المصفوفة
sum = 0;
x = (1 << i);
for (int j = 0; j < n; j++ )
{
if (arr[j] & x)
sum++;
}
// البتات التي لا يكون مجموعها من مضاعفات العدد 3
// هي البتات الخاصة العنصر الوحيد في المصفوفة
if (sum % 3)
result |= x;
}
return result;
}
// اختبار الدالة السابقة
int main()
{
int arr[] = {12, 1, 12, 3, 12, 1, 1, 2, 3, 2, 2, 3, 7};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "The element with single occurrence is " << getSingle(arr, n);
return 0;
}
- بايثون:
INT_SIZE = 32
def getSingle(arr, n) :
# تهيئة النتيجة
result = 0
# المرور على جميع البتات
for i in range(0, INT_SIZE) :
# حساب مجموع البتات في الدورة الحالية وفي جميع عناصر المصفوفة
sm = 0
x = (1 << i)
for j in range(0, n) :
if (arr[j] & x) :
sm = sm + 1
# البتات التي لا يكون مجموعها من مضاعفات العدد 3
# هي البتات الخاصة العنصر الوحيد في المصفوفة
if (sm % 3) :
result = result | x
return result
# اختبار الدالة السابقة
arr = [12, 1, 12, 3, 12, 1, 1, 2, 3, 2, 2, 3, 7]
n = len(arr)
print("The element with single occurrence is "
,getSingle(arr, n))
- جافا:
class GFG
{
static final int INT_SIZE = 32;
static int getSingle(int arr[], int n)
{
int result = 0;
int x, sum;
// المرور على جميع البتات
for(int i=0; i<INT_SIZE; i++)
{
// حساب مجموع البتات في الدورة الحالية وفي جميع عناصر المصفوفة
sum = 0;
x = (1 << i);
for(int j=0; j<n; j++)
{
if((arr[j] & x) == 0)
sum++;
}
// البتات التي لا يكون مجموعها من مضاعفات العدد 3
// هي البتات الخاصة العنصر الوحيد في المصفوفة
if ((sum % 3) == 0)
result |= x;
}
return result;
}
// اختبار التابع السابق
public static void main(String args[])
{
int arr[] = {12, 1, 12, 3, 12, 1, 1, 2, 3, 2, 2, 3, 7};
int n = arr.length;
System.out.println("The element with single occurrence is " + getSingle(arr, n));
}
}
تعطي الشيفرات السابقة المخرجات التالية:
The element with single occurrence is 7
التعقيد الزمني
يبلغ التعقيد الزمني لهذه الطريقة المقدار O(n)، وتستهلك مساحة قدرها O(1) من الذاكرة.
الطريقة الثالثة
تتبع هذه الطريقة الخطوات التالية:
- تجمع الخوارزمية الأعداد فرادى وتضرب المجموع بالعدد
3، وبذلك نحصل على ثلاثة أضعاف مجموع كل عنصر في المصفوفة. - تطرح الخوارزمية مجموع جميع الأعداد في المصفوفة من الرقم الذي حصلت عليه في الخطوة السابقة، ثم تقسم الناتج على
2. - نتيجة القسمة في الخطوة السابقة هو الرقم الذي يظهر في المصفوفة مرة واحدة فقط.
مثال:
arr[] = {12, 1, 12, 3, 12, 1, 1, 2, 3, 3}
Required no = ( 3*(sum_of_array_without_duplicates) - (sum_of_array) ) / 2
= ( 3*(12 + 1 + 3 + 2) - (12 + 1 + 12 + 3 + 12 + 1 + 1 + 2 + 3 + 3))/2
= ( 3* 18 - 50) / 2
= (54 - 50) / 2
= 2 (required answer)
تنفيذ الخوارزمية
من المعلوم أنّ المجموعات sets لا تسمح بتكرار العناصر فيها، ولكن تستخدم std::set عادة كشجرة بحث أحمر-أسود ثنائية red-black binary search tree، إذ يبلغ التعقيد الزمني لعملي إدراج العناصر في هذا النوع من بنى المعطيات المقدار O(log(n)) في أسوأ الحالات، وذلك لأنّ الشجرة تبقى متوازنة.
تعرض الأمثلة التالية طريقة تنفيذ الخوارزمية في عدد من لغات البرمجة:
- C++:
#include <bits/stdc++.h>
using namespace std;
int singleNumber(int a[],int n)
{
unordered_set<int> s(a,a+n);
int arr_sum=accumulate(a, a+n,0); // مجموع عناصر المصفوفة
int set_sum = accumulate(s.begin(), s.end(),0; // مجموع عناصر المجموعة
// تطبيق الصيغة الرياضية
return (3*set_sum-arr_sum)/2;
}
// اختبار الدالة السابقة
int main() {
int a[]={12, 1, 12, 3, 12, 1, 1, 2, 3, 2, 2, 3, 7};
int n=sizeof(a) / sizeof(a[0]);
cout<<"The element with single occurrence is "<<singleNumber(a,n);
}
- بايثون:
def singleNumber(nums):
# تطبيق الصيغة الرياضية
return (3 * sum(set(nums)) - sum(nums)) / 2
# اختبار الدالة السابقة
a = [12, 1, 12, 3, 12, 1, 1, 2, 3, 2, 2, 3, 7]
print ("The element with single occurrence is ",
int(singleNumber(a)))
- جافا:
import java.util.*;
class GFG
{
static int singleNumber(int a[], int n)
{
HashSet<Integer> s = new HashSet<Integer>();
for (int i : a)
{
s.add(i);
}
int arr_sum = 0;// مجموع عناصر المصفوفة
for (int i : a)
{
arr_sum += i;
}
int set_sum = 0;// مجموع عناصر المجموعة
for (int i : s)
{
set_sum += i;
}
// تطبيق الصيغة الرياضية
return (3 * set_sum - arr_sum) / 2;
}
// اختبار التابع السابق
public static void main(String[] args)
{
int a[] = {12, 1, 12, 3, 12, 1, 1, 2, 3, 2, 2, 3, 7};
int n = a.length;
System.out.println("The element with single " +
"occurrence is " + singleNumber(a, n));
}
}
تعطي الشيفرات السابقة المخرجات التالية:
The element with single occurrence is 7
التعقيد الزمني
يبلغ التعقيد الزمني لهذه الطريقة المقدار O(nlogn)، وتستهلك مساحة قدرها O(n) من الذاكرة.
مصادر
- صفحة Find the element that appears once في توثيق الخوارزميات في موقع GeeksforGeeks.