Массивтен максималды қайталанатын санды табыңыз


Күрделілік дәрежесі оңай
Жиі кіреді Adobe Amazon алма Bloomberg Цитадель еВау Facebook Голдман Сакс Google Intuit Microsoft Нутаниx PayPal Salesforce VMware тілек Yahoo
Array Zynga

Проблемалық мәлімдеме

«Массивтен қайталанатын максималды санды табу» мәселесінде біз сұрыпталмаған мәлімет бердік массив Берілген жиымға {0, k} диапазонындағы сандар кіреді, мұндағы k <= N. Жиымдағы ең көп рет келетін санды табыңыз.

Кіріс форматы

N бүтін санынан тұратын бірінші және жалғыз жол.

Кіріс жиымын білдіретін n бос орынмен бөлінген бүтін саннан тұратын екінші жол.

Шығу форматы

Массивтің ең көп рет келетін санын көрсететін бүтін санды қамтитын бірінші және жалғыз жол.

Шектеу

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

мысал

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

Түсіндіру: 3 берілген жиымдағы кез-келген саннан 5 есе көп келеді.

5
2 5 4 3 2
2

Түсіндіру: 2 берілген жиымдағы кез-келген саннан 2 есе көп келеді.

Алгоритм

  •  Берілген жиым элементін элементтер бойынша қайталау.
  • Массивтің әр элементі үшін біз [массив [i]% n] = массив [массив [i]% n] + n массивін жасаймыз.
  • Массивте қайталауды аяқтағаннан кейін массивтегі максималды элементтің индексін табыңыз.
  • Индекс максималды қайталанатын элемент болып табылады.
  • Түпнұсқа массивті қайтару үшін оны барлық элементтер үшін жасаңыз, массив [i] = массив [i]% k

Іске асыру

Массивте қайталанатын максималды санды табуға арналған C ++ бағдарламасы

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

Массивте қайталанатын максималды санды табуға арналған Java бағдарламасы

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

Күрделілікті талдау

Уақыттың күрделілігі

O (N) қайда n - бұл берілген массивтің өлшемі. Мұнда біз жай ғана бүкіл массивті айналып өтіп, әр позиция үшін операцияны тұрақты уақытта орындаймыз.

Ғарыштың күрделілігі

O (1) өйткені біз бұл жерде ешқандай қосалқы кеңістікті қолданбаймыз.