정수 배열에서 첫 번째 반복 요소 찾기

난이도 쉽게
자주 묻는 질문 아마존 광신자 MAQ Microsoft 신탁
배열 해싱조회수 34

문제 정책

에서 첫 번째 반복 요소 찾기 정렬 정수 문제는 정수 배열이 주어 졌다는 것을 나타냅니다. 배열에서 첫 번째 반복 요소를 찾아 해당 번호를 인쇄하도록 요청합니다.

arr[] = {2,6,9,3,1,9,1}
9

설명 : 주어진 배열에는 반복되는 두 개의 숫자가 있지만 첫 번째 반복은 9입니다.

arr[] = {1,4,7,0,2,5}
No repeating number.

설명 : 주어진 배열에 반복되는 숫자가 없습니다.

첫 번째 반복 문자를 찾는 알고리즘

1. Set flag to -1.
2. Declare a Set.
3. Start traversing the array from the right to left.
    1. If the number is repeating then update the value of flag to the index of the current array element.
    2. Else, insert the each array’s element into the declared set.
4. Check if flag value is still -1, then we have found no repeating element.
5. Else print flag index position of array.

설명

정수 배열에서 첫 번째 반복 요소 찾기

 

우리는 정수 배열을 주었고 반복 요소가 있는지 확인한 다음 인쇄하도록 요청했지만, 조건은 배열의 숫자가 첫 번째 반복 요소 여야한다는 것입니다. 배열에서 가장 먼저 반복되는 숫자가 필요한 대답이 될 것입니다. 즉, 오른쪽에서 왼쪽으로 이동하는 이유입니다. 우리는 세트를 사용합니다. 세트에는 공통 요소를 세트에 저장하지 않는 기능이 있습니다. 그래서 우리가 배열에서 반복되는 것을 발견했을 때 우리는 단순히 그 인덱스를 얻고 그 인덱스의 요소를 인쇄합니다.

집합을 선언하고 배열의 오른쪽에서 순회를 시작합니다. 집합에 현재 배열 요소의 값이 포함되어 있는지 확인한 다음 해당 인덱스를 가져 와서 플래그 값을 해당 인덱스로 업데이트합니다. 색인으로 사용하고 나중에 해당 값을 인쇄합니다.

그 전에 순회하는 동안 배열의 모든 값을 삽입해야하므로 비슷한 값을 얻으면 해당 요소의 인덱스를 저장하게됩니다. 오른쪽에서 배열을 탐색하고 있지만 오른쪽에서 왼쪽에서 반복되는 요소를 발견하면 첫 번째 반복 요소임을 의미합니다. 나중에 플래그 값이 여전히 -1인지 또는 업데이트되었는지 확인하기 때문에 플래그 값을 업데이트하고 있습니다. 여전히 -1이면 반복되는 요소를 찾지 못했음을 의미하고, 업데이트되면 배열의 플래그 인덱스 값을 인쇄합니다.

암호

첫 번째 반복 문자를 찾는 C ++ 코드

#include<bits/stdc++.h>

using namespace std;

void getFirstRepeatedElement(int arr[], int n)
{
    int Flag = -1;

    unordered_set<int> SET;

    for (int i = n - 1; i >= 0; i--)
    {
        if (SET.find(arr[i]) != SET.end())
            Flag = i;

        else
            SET.insert(arr[i]);
    }
    if (Flag!= -1)
        cout << "The first repeating element is " << arr[Flag];
    else
        cout << "There are no repeating elements";
}
int main()
{
    int arr[] = {2,6,9,3,1,9,1};

    int n = sizeof(arr) / sizeof(arr[0]);
    getFirstRepeatedElement (arr, n);
}
The first repeating element is 9

첫 번째 반복 문자를 찾는 Java 코드

import java.util.HashSet;

class FirstRepeatingElement
{
    public static void getFirstRepeatedElement (int arr[])
    {
        int Flag = -1;

        HashSet<Integer> SET = new HashSet<>();

        for (int i=arr.length-1; i>=0; i--)
        {
            if (SET.contains(arr[i]))
                Flag = i;

            else
                SET.add(arr[i]);
        }
        if (Flag!= -1)
            System.out.println("First repeating element is " + arr[Flag]);
        else
            System.out.println("No repeated element");
    }
    public static void main (String[] args)
    {
        int arr[] = {2,6,9,3,1,9,1};
        getFirstRepeatedElement(arr);
    }
}
First repeating element is 9

복잡성 분석

시간 복잡성

O (N) 어디에 "엔" 배열의 요소 수입니다. HashSet을 사용하고 있으므로 O (1) 연산에서 삽입 및 검색을 수행 할 수 있습니다.

공간 복잡성

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

Translate »