배열에서 최대 반복 수 찾기

난이도 쉽게
자주 묻는 질문 어도비 벽돌 아마존 Apple 블룸버그 게시물에서 이베이 Facebook 골드만 삭스 구글 인튜이트 Microsoft 뉴타 닉스 페이팔 세일즈 포스 VM웨어 Wish Yahoo
배열 Zynga조회수 1052

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 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) 여기에 보조 공간을 사용하지 않기 때문입니다.

균열 시스템 설계 인터뷰
Translate »