عنصر الأغلبية


مستوى الصعوبة سهل
كثيرا ما يطلب في أدوبي أمازون أجهزة آبل Atlassian بلومبرغ ByteDance Facebook GoDaddy أو جوجل Microsoft أوراكل لقب Snapchat Splunk ياهو Zenefits
مجموعة

المشكلة بيان

بالنظر إلى مصفوفة مرتبة ، نحتاج إلى إيجاد عنصر الأغلبية من المصفوفة المرتبة. عنصر الأغلبية: عدد أكثر من نصف حجم مجموعة. لقد قدمنا ​​هنا رقمًا x يتعين علينا التحقق من أنه عنصر الأغلبية أم لا.

مثال

إدخال

5 2

1 2 2 2 4

الناتج

2 هو عنصر الأغلبية

الطريقة 1 لإيجاد عنصر الأغلبية

نحن نستخدم مفهوم البحث الثنائي ولكن بطريقة خادعة. يمكن تعديل البحث الثنائي بسهولة للتحقق من التواجد الأول للرقم المحدد x.

خوارزمية

1. تحقق مما إذا كان العنصر الأوسط في المصفوفة x أم لا ، لأن أي عنصر غالبية يجب أن يكون في منتصف المصفوفة إذا حدث أكثر من N / 2 مرات
2. إذا كان موجودًا ، فقم بإجراء بحث ثنائي مخصص للعثور على التواجد الأول لـ x.
3. المؤشر الذي تم الحصول عليه هو k ، ثم تحقق مما إذا كان الفهرس (k + N / 2) يحتوي أيضًا على x. إذا كانت الإجابة بنعم ، فإن س هو عنصر الأغلبية.

NOTE: استخدم الدالتين Lower_bound و above_bound STL للقيام بالمهمة بسهولة.

تطبيق

برنامج C ++ لإيجاد عنصر الأغلبية

#include<bits/stdc++.h>
using namespace std;
int main()
{    
  int n,x;
  cin>>n>>x;  
  int arr[n];
  for(int i=0;i<n;i++)
  {
     cin>>arr[i];
  }
  int low=lower_bound(arr,arr+N,x)-arr; //index of first occurence of the element
  int high=upper_bound(arr,arr+N,x)-arr; //index of the last occurenece of element
  if(high-low>N/2)
    cout<<x <<" is a majority element\n";
  else
    cout<<x <<" is not a majority element\n";
  return 0;
}

برنامج جافا لإيجاد عنصر الأغلبية

import java.util.Scanner;
class sum
{
    public static int first(int arr[], int low, int high, int x, int n)
    {
        if (high >= low) {
            int mid = low + (high - low) / 2;
            if ((mid == 0 || x > arr[mid - 1]) && arr[mid] == x)
                return mid;
            else if (x > arr[mid])
                return first(arr, (mid + 1), high, x, n);
            else
                return first(arr, low, (mid - 1), x, n);
        }
        return -1;
    }
    public static int last(int arr[], int low, int high, int x, int n)
    {
        if (high >= low) {
            int mid = low + (high - low) / 2;
            if ((mid == n - 1 || x < arr[mid + 1]) && arr[mid] == x)
                return mid;
            else if (x < arr[mid])
                return last(arr, low, (mid - 1), x, n);
            else
                return last(arr, (mid + 1), high, x, n);
        }
        return -1;
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int x = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        int low=first(a,0,n-1,x,n); //index of first occurence of the element
        int high=last(a,0,n-1,x,n); //index of the last occurenece of element
        if((high-low+1)>n/2)
          System.out.println(x+" is a majority element");
        else
          System.out.println(x+" is not a majority element");
    }
}
5 2
1 2 2 2 4
2 is a majority element

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

تعقيد الوقت: O (logN) لأننا نستخدم مفهوم البحث الثنائي ونعلم أن خوارزمية البحث الثنائي لها تعقيد زمني O (طويل).

تعقيد الفضاء: O (1) لأننا نستخدم فقط بعض المتغيرات التي تندرج تحت O (1) أو التعقيد المكاني الثابت.

الطريقة 2 لإيجاد عنصر الأغلبية

خوارزمية

حلقة حتى نصف المصفوفة تفعل:
a. إذا كان العنصر الحالي هو x ، فتحقق مما إذا كان (الفهرس الحالي + N / 2) يحتوي على x.
b. إذا كان الأمر كذلك ، فإن س هو عنصر الأغلبية.
c. لا تعتبر س أخرى عنصرًا الأغلبية.

تطبيق

برنامج C ++

#include <bits/stdc++.h>
using namespace std;
int main()
{  
  int N,x;
  cin>>N>>x;
  int arr[N];
  for(int i=0;i<N;i++)
  {
      cin>>arr[i];
  }
  int end;
  if(N%2)
    end = N/2+1;
  else
    end = N/2;
    
  for(int i=0;i<end;i++)
  {
    if(arr[i] ==x and x == arr[i+N/2])
    {
      cout << x <<" is a mojority element "  <<endl;
      return 0;
    }
  }
  cout<<x<<" is not a majority element\n";
}

برنامج جافا 

import java.util.Scanner;
class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int x = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        int end;
        if(n%2==1)
          end = n/2+1;
        else
          end = n/2;
        int temp=0;
        for(int i=0;i<end;i++)
        {
          if(a[i] ==x && x == a[i+n/2])
          {
            System.out.println(x+" is a mojority element");
            i=end;
            temp=1;
          }
        }
        if(temp==0)
        System.out.println(x+" is not a majority element");
    }
}
5 2
1 2 3 3 6
2 is not a majority element

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

تعقيد الوقت: O (N) لأننا نجتاز نصف المصفوفة الفرعية التي تقودنا إلى تعقيد الوقت O (n).

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

مراجع