Çoxluq elementi

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Çiy kərpic Amazon alma Atlassian Bloomberg ByteDance Facebook GoDaddy google microsoft Kahin bölmə Snapchat Boşalmaq Yahoo Zenefits
GeyimBaxılıb 435

Problem bəyanat

Sıralanmış bir sıra nəzərə alınmaqla, sıralanmış massivdən əksəriyyət elementini tapmalıyıq. Çoxluq elementi: Sayıların yarısından çoxu meydana gəlir array. Burada x rəqəmi verdik, əksəriyyətin_element olduğunu yoxlamalıyıq.

misal

Input

5 2

1 2 2 2 4

Buraxılış

2 əksəriyyət elementidir

Çoxluq Elementini tapmaq üçün yanaşma 1

İkili axtarış konsepsiyasından istifadə edirik, amma hiyləgər bir şəkildə. Verilən x rəqəminin ilk meydana çıxmasını yoxlamaq üçün ikili axtarış asanlıqla dəyişdirilə bilər.

Alqoritm

1. Dizinin orta elementinin x olub olmadığını yoxlayın .Çünki hər hansı bir əksəriyyət_element N / 2 dəfədən çox baş verərsə, massivin ortasında olmalıdır.
2. Mövcud olduqda x-nin ilk meydana gəlməsini tapmaq üçün xüsusi bir İkili Axtarış edin.
3. Əldə olunan indeks k deyilir, sonra (k + N / 2) -ci indeksin də x olduğunu yoxlayın. Varsa x çoxluq_elementidir.

QEYD: Tapşırığı asanlıqla yerinə yetirmək üçün alt və yuxarı_bound STL funksiyalarından istifadə edin.

Həyata keçirilməsi

Çoxluq Elementini tapmaq üçün C ++ Proqramı

#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;
}

Çoxluq Elementini tapmaq üçün Java Proqramı

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi: O (logN), çünki ikili axtarış anlayışından istifadə edirik və bilirik ki, ikili axtarış alqoritminin O (uzun) zaman mürəkkəbliyi var.

Kosmik Mürəkkəblik: O (1), çünki yalnız O (1) altında olan bəzi dəyişənləri və ya daimi kosmik mürəkkəbliyi istifadə edirik.

Çoxluq Elementini tapmaq üçün yanaşma 2

Alqoritm

Dizinin yarısına qədər döngə edin:
a. İndiki element x olduqda, (indeks indeks + N / 2) -ci indeksin x-nin olub olmadığını yoxlayın.
b. Elədirsə x çoxluq_elementidir.
c. Else x əksəriyyət_element deyil.

Həyata keçirilməsi

C ++ Proqramı

#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";
}

Java Proqramı 

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi: O (N), çünki bizi yalnız O (n) zaman mürəkkəbliyinə aparan yarım alt dizini keçirik.

Kosmik Mürəkkəblik: O (1), çünki burada heç bir köməkçi yer istifadə etmirik.

References

Translate »