د اکثریت عنصر


مشکل کچه په اسانۍ سره
په مکرر ډول دننه پوښتل کیږي ایڈوب ترلاسه کړئ Amazon مڼه Atlassian د بلومبرګ ByteDance فیسبوک GoDaddy د ګوګل د Microsoft سينه_پوښ کړی Snapchat سپلک د ياهو زینتونه
پیشه

ستونزه بیان

ترتیب شوي صف کې ورکړل شوی ، موږ اړتیا لرو د ډلبلي شوي صف څخه اکثریت عنصر ومومو. د اکثریت عنصر: شمیره د سور. دلته موږ یو شمیره راکړې چې موږ یې باید وګورو چې دا د اکثریت برخه ده که نه.

بېلګه

ننوتۍ

5 2

1 2 2 2 4

Output

2 د اکثریت عنصر دی

د اکثریت عنصر موندلو لپاره 1 تګلاره

موږ د بائنري لټون مفهوم کار کوو مګر په پیچلي ډول. د بائنری لټون په اسانۍ سره تمدید کیدی شي ترڅو ورکړل شوي لمبر x لومړی پیښې وګوري.

الګوریتم

1. وګوره چې د صف منځنی عنصر x دی او که نه .ځکه چې اکثریت_لیمنٹ باید د صف په مینځ کې وي که چیرې دا د N / 2 ځله څخه ډیر پیښ شي.
2. که شتون ولري نو بیا د x لومړنۍ پیښې موندلو لپاره دودیز بائنري لټون ترسره کړئ.
3. لاسته راوړل شوی شاخص k دی ، بیا وګورئ چې (k + N / 2) th index هم x لري. که هو نو بیا x د اکثریت دی.

یادښت: د اسانه کار ترسره کولو لپاره د ټیټ_محدود او لوړ_او STDL افعال څخه کار واخلئ.

تطبیق

د اکثریت عنصر موندلو لپاره 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) th کې شاخص 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) ځکه چې دلته موږ کوم معاون ځای نه کاروو.

ماخذونه