Element większościowy

Poziom trudności Łatwo
Często zadawane pytania Adobe Amazonka Apple Atlassian Bloomberg ByteDance Facebook Idź Tato Google Microsoft wyrocznia sekcja Snapchat Splunk Yahoo Zenefity
Szykodwiedzajacy 499

Pytania do rozmowy kwalifikacyjnej na temat projektowania systemu może być tak nieograniczona, że ​​trudno jest określić właściwy sposób przygotowania. Teraz jestem w stanie złamać rundy projektowe Amazon, Microsoft i Adobe po zakupie ta książka. Codziennie poprawiaj jeden pytanie projektowe i obiecuję, że możesz złamać cały projekt.

Problem Statement

Mając posortowaną tablicę, musimy znaleźć większość elementów z posortowanej tablicy. Element większościowy: Liczba występująca w ponad połowie rozmiaru szyk. Tutaj podaliśmy liczbę x, którą musimy sprawdzić, czy jest to element większościowy, czy nie.

Przykład

Wkład

5 2

+1 (2) 2 2 4 XNUMX XNUMX +XNUMX (XNUMX) XNUMX XNUMX XNUMX XNUMX XNUMX +XNUMX XNUMX XNUMX XNUMX

Wydajność

2 to element większości

Podejście 1 do znajdowania elementu większościowego

Używamy koncepcji wyszukiwania binarnego, ale w skomplikowany sposób. Wyszukiwanie binarne można łatwo zmodyfikować, aby sprawdzić pierwsze wystąpienie podanej liczby x.

Algorytm

1. Sprawdź, czy środkowy element tablicy jest x, czy nie, ponieważ każdy element większościowy musi znajdować się w środku tablicy, jeśli występuje więcej niż N / 2 razy.
2. Jeśli jest obecny, wykonaj niestandardowe wyszukiwanie binarne, aby znaleźć pierwsze wystąpienie x.
3. Otrzymany indeks to powiedzmy k, a następnie sprawdź, czy (k + N / 2) -ty indeks również ma x. Jeśli tak, to x jest elementem większościowym.

UWAGA: Użyj funkcji lower_bound i high_bound STL, aby łatwo wykonać zadanie.

Realizacja

C ++ Program do znajdowania elementu większościowego

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

Program w języku Java do znajdowania elementu większościowego

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

Analiza złożoności

Złożoność czasowa: O (logN), ponieważ używamy koncepcji wyszukiwania binarnego i wiemy, że algorytm wyszukiwania binarnego ma złożoność O (długo) czasową.

Złożoność przestrzeni: O (1), ponieważ używamy po prostu niektórych zmiennych, które mieszczą się w O (1) lub stałej złożoności przestrzeni.

Podejście 2 do znajdowania elementu większościowego

Algorytm

Pętla do połowy tablicy wykonując:
a. Jeśli obecny element to x, sprawdź, czy (obecny indeks + N / 2) ten indeks zawiera x.
b. Jeśli tak, to x jest elementem większościowym.
c. W przeciwnym razie x nie jest elementem większościowym.

Realizacja

Program w 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";
}

Program Java 

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

Analiza złożoności

Złożoność czasowa: O (N), ponieważ po prostu przechodzimy przez pół podtablicę, która prowadzi nas do złożoności czasowej O (n).

Złożoność przestrzeni: O (1), ponieważ tutaj nie używamy żadnej spacji pomocniczej.

Referencje

Wywiady dotyczące projektowania systemu pękania
Translate »