배열에서 최대 반복 수 찾기

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

문제 정책

"배열에서 최대 반복 수 찾기"문제에서 정렬되지 않은 정렬 주어진 배열에는 {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 배가됩니다.

암호알고리즘

•  주어진 배열 요소를 요소별로 반복합니다.
• 배열의 모든 요소에 대해 array [array [i] % n] = array [array [i] % n] + n을 수행합니다.
• 배열에서 반복을 완료 한 후 배열에서 최대 요소의 인덱스를 찾으십시오.
• 인덱스는 최대 반복 요소입니다.
• 원래 배열을 다시 얻으려면 모든 요소에 대해 수행하십시오. array [i] = array [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) 여기에 보조 공간을 사용하지 않기 때문입니다.