أول عنصر غير مكرر


مستوى الصعوبة سهل
كثيرا ما يطلب في بلزبار كوملي ميديا [متليف Snapdeal Sprinklr ووكر
مجموعة مزيج البحث

لدينا المصفوفة A. علينا إيجاد أول عنصر غير مكرر في المصفوفة.

مثال

الإدخال:

أ [] = {2,1,2,1,3,4،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX}

الإخراج:

أول عنصر غير مكرر هو: 3

لأن 1 ، 2 ليست الإجابة لأنها تتكرر و 4 ليست الإجابة لأن علينا إيجاد العنصر الأول غير المتكرر ، وهو 3 وليس 4.

النهج 1: القوة الغاشمة

الفكرة الرئيسية

لكل عنصر في مجموعة، سنقوم بتكرار المصفوفة بأكملها وإذا كان هذا العنصر غير مكرر ، فسنقوم فقط بطباعة هذا العنصر.

خوارزمية

  1. قم بتشغيل حلقة لـ I في النطاق من 0 إلى n-1
    1. قم بتشغيل حلقة لـ j في النطاق من 0 إلى n
      1. إذا كانت j تساوي n ، فقم بطباعة A [i] وأعد.
      2. إذا لم تكن I مساوية لـ j و A [i] تساوي A [j] ، فقم بالانفصال عن هذه الحلقة.
    2. اطبع أن جميع العناصر تتكرر في المصفوفة.

التنفيذ للعنصر الأول غير المتكرر

برنامج C ++

#include <bits/stdc++.h>
using namespace std;
void firstNonRepeatingElement(vector<int> &A)
{
    int n = A.size();
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j <= n; j++)
        {
            if (j == n)
            {
                cout << "First non-repeating element is: " << A[i] << endl;
                return;
            }
            if (j != i and A[i] == A[j])
            {
                break;
            }
        }
    }
    cout << "All the elements are repeating." << endl;
}
int main()
{
    vector<int> A = {2, 1, 2, 1, 3, 4};
    firstNonRepeatingElement(A);
    return 0;
}
First non-repeating element is: 3

برنامج جافا

public class Main
{
    static void firstNonRepeatingElement(int A[])
    {
        int n = A.length;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j <= n; j++)
            {
                if (j == n)
                {
                    System.out.println("First non-repeating element is: "+A[i]);
                    return;
                }
                if (j != i && A[i] == A[j])
                {
                    break;
                }
            }
        }
        System.out.println("All the elements are repeating.");
    }
  public static void main(String[] args) {
    int A[]={2, 1, 2, 1, 3, 4};
    firstNonRepeatingElement(A);
  }
}
First non-repeating element is: 3

تحليل التعقيد لأول عنصر غير متكرر

تعقيد الوقت

لدينا حلقتان متداخلتان بحجم N ، وبالتالي فإن التعقيد الزمني الإجمالي هو O (N ^ 2).

تعقيد الفضاء

نحن لا نستخدم أي مساحة إضافية ، لذا فإن تعقيد الفضاء هو يا (1).

الأسلوب 2: استخدام التجزئة

الفكرة الرئيسية

يمكننا تخزين تكرار كل عنصر في جدول تجزئة وبعد ذلك يمكننا اجتياز المصفوفة وإيجاد العنصر الأول الذي يكون تردده 1.

خوارزمية

  1. قم بتخزين تكرار كل عنصر في جدول تجزئة.
  2. قم بتشغيل حلقة لـ I في النطاق من 0 إلى n-1
    1. إذا كان تكرار A [i] في جدول التجزئة هو 1 ، اطبع A [i] وأعد.
  3. اطبع أن هناك كل العناصر المكررة في المصفوفة.

افهم بقدوة

أ [] = {2 ، 1 ، 2 ، 1 ، 3 ، 4}

ثم سيبدو جدول التجزئة كما يلي:

أول عنصر غير مكرر

التنفيذ للعنصر الأول غير المتكرر

برنامج C ++

#include <bits/stdc++.h>
using namespace std;
void firstNonRepeatingElement(vector<int> &A)
{
    int n = A.size();
    unordered_map<int, int> hash_table;
    for (int i = 0; i < n; i++)
    {
        hash_table[A[i]]++;
    }
    for (int i = 0; i < n; i++)
    {
        if (hash_table[A[i]] == 1)
        {
            cout << "First non-repeating element is: " << A[i] << endl;
            return;
        }
    }
    cout << "All the elements are repeating." << endl;
}
int main()
{
    vector<int> A = {2, 1, 2, 1, 3, 4};
    firstNonRepeatingElement(A);
    return 0;
}
First non-repeating element is: 3

برنامج جافا

public class Main
{
    static void firstNonRepeatingElement(int A[])
    {
        java.util.HashMap<Integer, Integer> hash_table = new java.util.HashMap<Integer, Integer>();
        int n = A.length;
        for(int i=0;i<n;i++)
        {
            Integer freq = hash_table.get(A[i]);
            hash_table.put(A[i], (freq == null) ? 1 : freq + 1); 
        }

        for (int i = 0; i < n; i++)
        {
            if (hash_table.get(A[i])==1)
            {
                System.out.println("First non-repeating element is: "+A[i]);
                return;
            }
        }
        System.out.println("All the elements are repeating.");
    }
  public static void main(String[] args) {
    int A[]={2, 1, 2, 1, 3, 4};
    firstNonRepeatingElement(A);
  }
}
First non-repeating element is: 3

تحليل التعقيد لأول عنصر غير متكرر

تعقيد الوقت

نحن نكرر المصفوفة مرتين فقط حتى يصبح الوقت التعقيد الكلي على).

تعقيد الفضاء

نحن نحتفظ بجدول تجزئة لذا فإن تعقيد المساحة على).

المراجع