प्रमुख तत्व


कठिनाई स्तर आसान
में अक्सर पूछा एडोब वीरांगना सेब Atlassian ब्लूमबर्ग ByteDance Facebook पिताजी जाओ गूगल माइक्रोसॉफ्ट ओरेकल अनुभाग Snapchat Splunk याहू ज़ेनफ़िट्स
ऐरे

समस्या का विवरण

एक सॉर्ट किए गए सरणी को देखते हुए, हमें सॉर्ट किए गए सरणी से बहुमत तत्व को खोजने की आवश्यकता है। प्रमुख तत्व: संख्या आधे से अधिक आकार में होती है सरणी। यहां हमने एक नंबर x दिया है जिसे हमें यह जांचना है कि यह बहुमत है या नहीं।

उदाहरण

निवेश

5 2

1 2 2 2 4

उत्पादन

2 एक बहुसंख्यक तत्व है

बहुमत तत्व को खोजने के लिए 1 दृष्टिकोण

हम बाइनरी सर्च की अवधारणा का उपयोग करते हैं लेकिन एक ट्रिकी तरीके से। दी गई संख्या x की पहली घटना की जांच करने के लिए बाइनरी खोज को आसानी से संशोधित किया जा सकता है।

कलन विधि

1. चेक करें कि ऐरे का मध्य तत्व x है या नहीं। लेकिन यदि कोई एन / 2 बार से अधिक होता है, तो किसी भी बहुमत_सेलेमेंट को एरे के मध्य में होना चाहिए।
2. यदि मौजूद है तो x की पहली घटना को खोजने के लिए एक कस्टम बाइनरी सर्च करें।
3. प्राप्त सूचकांक को k कहा जाता है, फिर जांचें कि क्या (k + N / 2) वें सूचकांक में भी x है। यदि हाँ, तो 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 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. Else x एक बहुमत_मत नहीं है।

कार्यान्वयन

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) क्योंकि यहां हम किसी सहायक स्थान का उपयोग नहीं करते हैं।

संदर्भ