Dizidə Maksimum Təkrar Sayı tapın

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Çiy kərpic Amazon alma Bloomberg Citadel eBay Facebook Goldman Sachs google Intuit microsoft Nutanix PayPal Salesforce VMware Arzu Yahoo
Geyim ZyngaBaxılıb 1051

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

"Arrayda Maksimum Təkrar Sayı tap" problemində çeşidlənməmiş verdik array N ölçüsündə. Verilən massivdə {0, k} aralığında ədədlər var, burada k <= N. Massivdə maksimum dəfə gələn ədədi tapın.

Giriş Formatı

Bir n tam ədədi olan ilk və yalnız bir sətir.

Giriş sətrini göstərən n boşluqla ayrılmış tam ədədi olan ikinci sətir.

Çıxış formatı

Massivdə maksimum dəfə gələn rəqəmi göstərən tam ədədi ehtiva edən ilk və yalnız bir sətir.

Məhdudiyyətlər

  • 1 <= n <= 10 ^ 6
  • 1 <= a [i] <= n

misal

13
2 3 3 4 4 5 5 3 3 6 7 8 3
3

Explanation: 3, verilən sıradakı istənilən saydan maksimum 5 dəfə gəlir.

5
2 5 4 3 2
2

Explanation: 2, verilən sıradakı istənilən saydan maksimum 2 dəfə gəlir.

Alqoritm

  •  Verilən massiv elementini element ilə təkrarlayın.
  • Massivdəki hər bir element üçün [array [i]% n] = array [array [i]% n] + n array edirik.
  • Massivdə təkrarlamanı tamamladıqdan sonra massivdəki maksimum elementin indeksini tapın.
  • İndeks maksimum təkrarlanan elementdir.
  • Orijinal massivi geri qaytarmaq üçün bunu bütün elementlər üçün edin, massiv [i] = massiv [i]% k

Həyata keçirilməsi

Dizidəki Maksimum Təkrar Sayı Tapmaq üçün C ++ Proqramı

#include <bits/stdc++.h>
using namespace std;

int MaxRepertingElement(int* array, int n)
{
  //modify the array 
  for (int i = 0; i< n; i++)
  {
    array[array[i]%n] += n;
  }
  int max_element = INT_MIN,result = 0;
  for (int i = 0; i < n; i++)
  {
    if (array[i] > max_element)
    {
      max_element = array[i];
      result = i;
    }
  }
  //get the array back to original values
  for (int i = 0; i< n; i++)
  {
    array[i] = array[i]%n; 
  }
  return result;
}

int main()
{
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    cout<<MaxRepertingElement(a, n)<<endl;
    return 0;
}

Dizidəki Maksimum Təkrar Nömrəni Tapmaq üçün Java Proqramı

import java.util.Scanner;
class sum
{
    //Rearrange function  
    public static int MaxRepertingElement(int array[], int n)
    {
      //modify the array 
      for (int i = 0; i< n; i++)
      {
        array[array[i]%n] += n;
      }
      int max_element = -1,result = 0;
      for (int i = 0; i < n; i++)
      {
        if (array[i] > max_element)
        {
          max_element = array[i];
          result = i;
        }
      }
      //get the array back to original values
      for (int i = 0; i< n; i++)
      {
        array[i] = array[i]%n; 
      }
      return result;
    }
    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();
        }
        int ans = MaxRepertingElement(a, n);
        System.out.println(ans);
    }
}
5
1 1 1 2 3
1

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (n) hara n verilmiş massivin ölçüsüdür. Burada sadəcə bütün massivi keçirik və əməliyyatı hər mövqe üçün sabit vaxtda yerinə yetiririk.

Kosmik Mürəkkəblik

O (1) çünki burada heç bir köməkçi yerdən istifadə etmirik.

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