మెజారిటీ ఎలిమెంట్  


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది Adobe అమెజాన్ ఆపిల్ Atlassian బ్లూమ్బెర్గ్ ByteDance <span style="font-family: Mandali; ">ఫేస్‌బుక్ </span> GoDaddy గూగుల్ మైక్రోసాఫ్ట్ ఒరాకిల్ విభాగం Snapchat Splunk యాహూ జెనెఫిట్స్
అర్రే

సమస్యల నివేదిక  

క్రమబద్ధీకరించబడిన శ్రేణిని బట్టి, క్రమబద్ధీకరించబడిన శ్రేణి నుండి మెజారిటీ మూలకాన్ని కనుగొనాలి. మెజారిటీ మూలకం: సగం కంటే ఎక్కువ పరిమాణంలో సంభవించే సంఖ్య అమరిక. ఇక్కడ మనం x సంఖ్యను ఇచ్చాము, అది మెజారిటీ_ఎలిమెంట్ కాదా అని తనిఖీ చేయాలి.

ఉదాహరణ  

ఇన్పుట్

5 2

1 2 2 2 4

అవుట్పుట్

2 మెజారిటీ మూలకం

మెజారిటీ ఎలిమెంట్‌ను కనుగొనడం కోసం అప్రోచ్ 1  

మేము బైనరీ శోధన భావనను ఉపయోగిస్తాము కాని గమ్మత్తైన పద్ధతిలో. ఇచ్చిన సంఖ్య x యొక్క మొదటి సంఘటనను తనిఖీ చేయడానికి బైనరీ శోధనను సులభంగా సవరించవచ్చు.

అల్గారిథం

1. శ్రేణి యొక్క మధ్య మూలకం x లేదా కాదా అని తనిఖీ చేయండి .అందువల్ల ఏదైనా మెజారిటీ_ఎలిమెంట్ N / 2 కన్నా ఎక్కువ సార్లు సంభవిస్తే శ్రేణి మధ్యలో ఉండాలి.
2. ఉన్నట్లయితే, x యొక్క మొదటి సంఘటనను కనుగొనడానికి అనుకూల బైనరీ శోధన చేయండి.
3. పొందిన సూచిక k అని చెప్పండి, తరువాత (k + N / 2) వ సూచికలో x కూడా ఉందో లేదో తనిఖీ చేయండి. అవును అయితే x మెజారిటీ_ఎలిమెంట్.

గమనిక: పనిని సులభంగా చేయడానికి తక్కువ_బౌండ్ మరియు అధిక_బౌండ్ STL ఫంక్షన్లను ఉపయోగించండి.

అమలు

మెజారిటీ ఎలిమెంట్‌ను కనుగొనడానికి సి ++ ప్రోగ్రామ్

#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. అలా చేస్తే x మెజారిటీ_ఎలిమెంట్.
c. ఇతర x మెజారిటీ_ఎలిమెంట్ కాదు.

అమలు

సి ++ ప్రోగ్రామ్

#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) ఎందుకంటే ఇక్కడ మనం సహాయక స్థలాన్ని ఉపయోగించము.

ప్రస్తావనలు