1에서 N-1 사이의 유일한 반복 요소 찾기

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

1에서 N-1 문제 사이의 유일한 반복 요소를 찾기 위해 우리는 정렬 1에서 n-1 사이의 임의의 정수입니다. 반복되는 하나의 숫자가 있습니다. 당신의 임무는 그 번호를 찾는 것입니다.

예

입력

[2,3,4,5,2,1] A

산출

2

설명

2는 배열에서 두 번 나오는 요소입니다.

 

1에서 N-1 사이의 유일한 반복 요소를 찾기위한 알고리즘

1. 합계를 0으로 설정합니다.
2. i <n 인 동안 전체 배열을 횡단합니다.
   1. 합계 = sum + arr [i].
3. sum- (n * (n-1)) / 2를 반환합니다.

1에서 N-1 사이의 유일한 반복 요소 찾기에 대한 설명

우리는 배열에서 반복되는 숫자를 알아 내도록 요청하는 문제 (Find the Only Repetitive Element Between 1 to N-1) 문을 제공했습니다. 우리는 단순히 합계 공식. 사용 합계 공식, 반복되는 요소를 쉽게 식별 할 수 있습니다. 이름에서 알 수 있듯이 합계 공식 단순히 값을 합산하는 것을 의미합니다.

여기 루프에서 마지막 배열 요소를 방문 할 때까지 0 번째 위치에서 루프의 끝까지 배열을 탐색하기 시작합니다. 모든 반복과 array [i]의 각 값에 대해 sum과 함께 추가하고이를 합계에 저장하여 다음에 반복 할 때 sum의 초기화 된 값이 아닌 합계 값을 얻습니다. 0. 따라서 매 반복마다 합계로 저장된 일부 값이 있습니다.

반복되는 요소를 제공하는 공식을 만들거나 시리즈에 포함 된 추가 요소를 반환한다고 말할 수 있습니다. 연속적으로 1에서 5까지 주어진 시리즈가 있다고 가정합니다. 모든 숫자를 더하면 모든 숫자의 합이 주어지고 시리즈에서 반복되는 요소가 없습니다. 그리고 우리는 우리의 합 공식 인 sum – (n * (n-1)) / 2의 차이를 반환합니다.

예를 들어 보겠습니다.

arr = [2,3,4,5,2,1], 합계 = 0

0부터 시작하여 각 요소를 방문하는 전체 루프를 순회 할 수 있습니다. –>

i = 0;

sum = sum + arr [i] => sum = 2

i = 1;

sum = sum + arr [i] => sum = 5

i = 2;

sum = sum + arr [i] => sum = 9

i = 3;

sum = sum + arr [i] => sum = 14

i = 4;

sum = sum + arr [i] => sum = 16

i = 5;

sum = sum + arr [i] => sum = 17

1- (2 * (17-6)) / 6 인 sum- (n * (n-1)) / 2를 반환합니다.

17 – 15 = 2, 이것이 우리의 필수 출력입니다.

 

핀

1에서 N-1 사이의 유일한 반복 요소를 찾기위한 구현

C ++ 프로그램

#include<iostream>
using namespace std;
int getRepeatedElement(int arr[], int n)
{
    int sum = 0;
    for (int i = 0; i < n; i++)
    {
        sum = sum + arr[i];
    }
    return sum-(((n - 1) * n)/2);
}
int main()
{
    int arr[] = {1,5,3,2,6,4,7,8,4};
    int len = sizeof(arr)/sizeof(arr[0]);
    cout<<(getRepeatedElement(arr, len));
    return 0;
}

4

자바 프로그램

class repetitiveElement
{
    public static int getRepeatedElement(int[] arr, int n)
    {
        int sum = 0;
        for (int i = 0; i < n; i++)
        {
            sum = sum + arr[i];
        }
        return sum-(((n - 1) * n)/2);
    }
    public static void main(String args[])
    {
        int[] arr = {1,5,3,2,6,4,7,8,4};
        int len = arr.length;
        System.out.println(getRepeatedElement(arr, len));
    }
}

4

1에서 N-1 사이의 유일한 반복 요소 찾기를위한 복잡도 분석

시간 복잡성

O (N) 어디에 "엔" 배열의 요소 수입니다.

공간 복잡성

O (1) 여기에 보조 공간을 사용하지 않기 때문입니다.

참조