رقم واحد


مستوى الصعوبة سهل
كثيرا ما يطلب في أمازون
مجموعة

إعطاء مصفوفة [] بحجم n. جميع العناصر الموجودة في مجموعة موجودة مرتين باستثناء 1. ابحث عن العنصر الذي يظهر مرة واحدة فقط أو بعبارة أخرى نقول إنه يجد الرقم الفردي.

رقم واحد

مثال

الإدخال: أ [] = {1 ، 3 ، 5 ، 5 ، 2 ، 1 ، 3}

الإخراج: 2

الإدخال: أ [] = {1 ، 3 ، 5 ، 5 ، 1}

الإخراج: 3

طريقة بسيطة

تحقق من كل عنصر مع كل عنصر آخر. أعد العنصر الفردي.

خوارزمية

  1. تهيئة مصفوفة [] بحجم n.
  2. قم بإنشاء متغير عدد صحيح لتخزين العنصر الفردي في المصفوفة وتهيئة متغير العلم على أنه 0.
  3. اجتياز المصفوفة وتحديث متغير العلامة كـ 0 والمتغير للعنصر الفردي كقيمة مخزنة في الفهرس الحالي في المصفوفة a [].
  4. قم بإنشاء حلقة داخلية من 0 إلى n-1 وتحقق مما إذا كانت القيمة المخزنة في الفهرس الحالي في المصفوفة [] تساوي المتغير الخاص بالعنصر الفردي وأن الفهرس الحالي للحلقة الداخلية لا يساوي الفهرس الحالي لـ الحلقة الخارجية ، قم بتحديث متغير العلم كـ 1.
  5. إذا كان متغير العلم يساوي 0 ، فقم بإرجاع المتغير للعنصر الفردي.

برنامج C ++ للعثور على رقم واحد

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

int singleElement(int a[], int n){
    int single,flag=0;
    for(int i=0; i<n; i++){
        flag = 0;
        single = a[i];
        for(int j=0; j<n; j++){
            if((a[j]==single)&&(j!=i)){
                flag=1;
            }    
        }
        if(flag==0)
            return single;
    }
}

int main() {
  int a[] = {1, 3, 5, 5, 2, 1, 3};
  int n = sizeof(a)/sizeof(a[0]);
  cout<<singleElement(a, n);
  return 0;
}
2

برنامج Java للعثور على رقم واحد

class unique{ 
    
    static int singleElement(int[] a, int n){
        int single=0,flag=0;
        for(int i=0; i<n; i++){
            flag = 0;
            single = a[i];
            for(int j=0; j<n; j++){
                if((a[j]==single)&&(j!=i)){
                    flag=1;
                }    
            }
            if(flag==0){
                return single;
            }    
        }
        return single;
    }

    public static void main (String[] args){ 
  
        int a[] = {1, 3, 5, 5, 2, 1, 3}; 
        int n = a.length; 
        System.out.println(singleElement(a, n)); 
        
    } 
} 
2

تحليل التعقيد

تعقيد الوقت: على2) حيث n هو عدد العناصر في المصفوفة المعطاة a [].

مساحة إضافية: O (1) لأننا استخدمنا مساحة إضافية ثابتة.

باستخدام Xor

باستخدام خصائص xor -

أ x أو أ = 0

0 x أو a = أ

خوارزمية

  1. تهيئة مصفوفة [] بحجم n.
  2. قم بإنشاء دالة للعثور على العنصر الفردي في المصفوفة المعطاة [] الذي يقبل مصفوفة عدد صحيح وحجم مصفوفة الأعداد الصحيحة باعتبارها معلمة.
  3. قم بتهيئة متغير واحد وقم بتخزين العنصر الأول من المصفوفة المحددة فيه.
  4. اجتياز المصفوفة من 1 إلى n-1 وتحديث المتغير الفردي كـ xor للمتغير المنفرد نفسه والقيمة في الفهرس الحالي في المصفوفة المحددة.
  5. إرجاع المتغير الفردي.

برنامج C ++ للعثور على رقم واحد

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

int singleElement(int a[], int n){
    int single = a[0]; 
    for(int i=1; i<n; i++) 
        single = single ^ a[i]; 
  
    return single;
}

int main() {
  int a[] = {1, 3, 5, 5, 2, 1, 3};
  int n = sizeof(a)/sizeof(a[0]);
  cout<<singleElement(a, n);
  return 0;
}
2

برنامج Java للعثور على رقم واحد

class unique{ 
    
    static int singleElement(int[] a, int n){
        int single = a[0]; 
        for(int i=1; i<n; i++) 
            single = single ^ a[i]; 
      
        return single;
    }

    public static void main (String[] args){ 
  
        int a[] = {1, 3, 5, 5, 2, 1, 3}; 
        int n = a.length; 
        System.out.println(singleElement(a, n)); 
        
    } 
} 
2

تحليل التعقيد

تعقيد الوقت: O (n) حيث n هو عدد العناصر في المصفوفة المعطاة a [].

مساحة إضافية: O (1) لأننا استخدمنا مساحة إضافية ثابتة.

المراجع