Bir Array Liderləri tapın

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Amazon Goldman Sachs PayU
GeyimBaxılıb 977

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat

N elementi olan bir sıra verilmişdir. An liderlərini tapın array. Liderlər massivdə özlərindən daha böyük bir elementi olmayan elementdir.

misal

Input

7

1 95 4 46 8 12 21

Buraxılış

95 46 21

Izahat

Burada sağ tərəfdə yuxarıdakı rəqəmlərdən daha yüksək olan heç bir element yoxdur.

Yuxarıda göstərilən nümunədə, son element (yəni 21) hər zaman liderdir, çünki onun sağında heç bir element yoxdur. 46, 95, liderlərdir, çünki heç bir element massivin sağındakı onlardan daha böyük deyildir.

Yanaşma 1

Alqoritm

1. Dizini sondan başlanğıc tərəfə keçməyə başlayın.
2. Əldə olunan cari maksimumu izləyin.
3. Hər bir element üçün, element cari maksimumdan böyükdürsə, bu liderdir, çünki sağında ondan böyük bir rəqəm yox idi. Sonra sadəcə elementi yazdırın və yeni cari maksimuma çevirin.
4. Başqaları əvvələ qədər sürməyə davam edin.

Həyata keçirilməsi

Bir Dizidəki Liderləri Tapmaq üçün C ++ Proqramı

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N;//size of the array
    cin>>N;
    int arr[N];
    for(int i=0;i<N;i++)
    {
      cin>>arr[i];
    }
    cout<<"Leaders are : \n";  
    int cur_max = INT_MIN;
  
    for(int i = N-1; i>=0 ; i--)
    {
      if(arr[i] > cur_max)
        {
          cout << arr[i] <<" ";
          cur_max = arr[i];
        }
    }
  
  return 0;
}

Bir Dizidəki Liderləri Tapmaq üçü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 a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        System.out.println("Leaders are : ");  
        int cur_max = -1;
        for(int i=n-1;i>=0;i--)
        {
          if(a[i]>cur_max)
          {
              System.out.print(a[i]+" ");
              cur_max = a[i];
          }
        }
     }
}
7
1 95 4 46 8 12 21
Leaders are : 
21 46 95

Bir Dizidəki Liderləri Tapmaq üçün Mürəkkəblik Təhlili

Zamanın mürəkkəbliyi 

O (N) burada n massivin ölçüsüdür. Burada sıra sonundan keçirik və massivdəki liderləri yoxlayırıq.

Kosmik Mürəkkəblik

O (1) çünki həllini tapmaq üçün bir neçə dəyişəndən istifadə edirik.

Yanaşma 2

Alqoritm

1. Dizini başdan sona qədər keçməyə başlayın.
2. Bütün elementləri bir-bir seçin, Hər seçilmiş element üçün elementləri sağ tərəfində müqayisə edin.
a. Əgər seçilmiş element bütün elementlərdən sağ tərəfindədirsə, seçilmiş element liderdir.
b. başqa, lider deyil.

Həyata keçirilməsi

Bir Dizidəki Liderləri Tapmaq üçün C ++ Proqramı

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N;//size of the array
    cin>>N;
    int arr[N];
    for(int i=0;i<N;i++)
    {
      cin>>arr[i];
    }
    cout<<"Leaders are : \n";
    for(int i = 0; i < N; i++) // select an element
    {
      bool leader = true; // assume it to be greater than all the elements on the right side
      for(int j = i+1; j<N; j++)// loop through all the elements in the right of the selected element
        {
          if(arr[j] > arr[i])//if the element on right is larger then the selected element is not a leader
            {
              leader = false;
              break;
            }
        }
      if(leader)
      cout<<arr[i]<<" ";
    }
  return 0;
}

Bir Dizidəki Liderləri Tapmaq üçü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 a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        System.out.println("Leaders are : ");  
        for(int i = 0; i < n; i++) // select an element
        {
          boolean leader = true; // assume it to be greater than all the elements on the right side
          for(int j = i+1; j<n; j++)// loop through all the elements in the right of the selected element
            {
              if(a[j] > a[i])//if the element on right is larger then the selected element is not a leader
                {
                  leader = false;
                  break;
                }
            }
          if(leader)
          System.out.print(a[i]+" ");
        }
     }
}
7
1 95 4 46 8 12 21
Leaders are : 
95 46 21

Bir Dizidəki Liderləri Tapmaq üçün Mürəkkəblik Təhlili

Zamanın mürəkkəbliyi 

O (N * N) burada N massivin ölçüsüdür. Burada sıradakı liderləri yoxlamaq üçün ith elementi üçün Ni dəfə keçirik. Bu, bizi N * N zaman mürəkkəbliyinə aparacaqdır.

Kosmik Mürəkkəblik

O (1) çünki həllini tapmaq üçün bir neçə dəyişəndən istifadə edirik.

References

Crack Sistemi Dizayn Müsahibələri
Translate »