중복 요소 찾기

난이도 중급
자주 묻는 질문 Apple 블룸버그 게시물에서 구글 Microsoft
배열 이진 검색 두 포인터조회수 65

주어진 정렬 배열의 각 요소가 1과 n (포함) 사이 인 경우 n + 1 크기의 정수로 배열에 중복 요소가 하나있는 경우 중복 요소를 찾습니다.

무차별 대입 방법 – 중복 요소 찾기에 대한 접근 방식 1

모든 i 번째 요소에 대해 (i + 1)에서 n까지 주어진 배열에 대해 루프를 실행하고 i 번째 요소가 있는지 확인합니다.

중복 요소 찾기를위한 복잡성 분석

공간 복잡성 : O (1)

시간 복잡도 : O (n ^ 2)

C ++ 프로그램

#include<bits/stdc++.h>
using namespace std;

int findDuplicate(int a[],int n){
    for(int i=0;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            if(a[i]==a[j]){            // Duplicate element found
                return a[i];
            }
        }
    }
    return -1;                         // invalid input
}

int main(){
    int n;
    cin>>n;
    int a[n+1];
    for(int i=0;i<n+1;i++){
        cin>>a[i];
    }
    int ans = findDuplicate(a,n);
    cout<<"Duplicate element is: "<<ans;
}
6
6 5 1 2 6 3 4
Duplicate element is: 6

JAVA 프로그램

import java.util.*;
public class Main
{
    public static int findDuplicate(int[] a,int n){ 
        for(int i=0;i<=n;i++){ 
            for(int j=i+1;j<=n;j++){ 
                if(a[i]==a[j]){ // Duplicate element found 
                    return a[i]; 
                } 
            } 
        } 
        return -1; // invalid input 
    }
  public static void main(String[] args) {
      Scanner sc= new Scanner(System.in); 
      int n = sc.nextInt();
        int[] a = new int[n+1]; 
        for(int i=0;i<n+1;i++){ 
            a[i] = sc.nextInt(); 
        } 
        int ans = findDuplicate(a,n); 
    System.out.println("Duplicate element is: "+ans);
  }
}

5
1 4 2 3 3 5
Duplicate element is: 3

해싱 사용 – 접근 방식 2

암호알고리즘

Step1: 각 요소의 빈도를 저장할 해시 맵을 만듭니다.

Step2: 배열 XNUMX을 탐색하고 해시 맵에서 각 요소의 빈도를 업데이트합니다.

단계 3: 해시 맵을 순회하고 빈도 2의 요소를 반환합니다.

중복 요소 찾기를위한 복잡성 분석

공간 복잡도 : O (n), 우리는 최악의 경우 n의 크기를 갖는 해시의 for에 추가 메모리를 사용하고 있습니다.

시간 복잡도 : O (n), 각 숫자의 빈도를 계산하기 위해 배열을 한 번 탐색해야합니다. 그런 다음지도를 횡단하여 빈도가 1보다 큰 요소를 찾습니다.

C ++ 프로그램

#include<bits/stdc++.h>
using namespace std;

int findDuplicate(int a[],int n){
    unordered_map<int,int> u;
    for(int i=0;i<=n;i++){
        if(u.find(a[i])==u.end()){
            u.insert(make_pair(a[i],1));
        }
        else{
            u[a[i]]++;
        }
    }
    for(auto it=u.begin();it!=u.end();it++){
        if(it->second == 2){            // the element is duplicate if it's frequency is more that 1
            return it->first;
        }
    }
    return -1;                 // in case of invalid input
}

int main(){
    int n;
    cin>>n;
    int a[n+1];
    for(int i=0;i<n+1;i++){
        cin>>a[i];
    }
    int ans = findDuplicate(a,n);
    cout<<"Duplicate element is: "<<ans;
}
5
5 2 4 1 2 3
Duplicate element is: 2

Xor 속성 사용 – 중복 요소 찾기 방법 3

a ^ a = 0 및 a ^ 0 = a

암호알고리즘

단계 1: 1에서 n까지의 xor를 찾아 변수 X에 저장합니다.

단계 2: 주어진 배열의 xor를 찾아 변수 Y에 저장합니다.

단계 3: duplicate_element를 찾기 위해 X와 Y의 xor를 취하십시오.

중복 요소 찾기를위한 복잡성 분석

공간 복잡성 : O (1), 입력 배열에서 추가 메모리를 사용하지 않습니다.

시간 복잡성 : O (n), 배열을 한 번만 탐색해야합니다. 여기서 n은 주어진 배열의 크기입니다.

C ++ 프로그램

#include<bits/stdc++.h>
using namespace std;

int findDuplicate(int a[],int n){
    int X=0,Y=0;
    for(int i=1;i<=n;i++){
        X = X^i;
    }
    for(int i=0;i<=n;i++){
        Y = Y^a[i];
    }
    return X^Y;
}

int main(){
    int n;
    cin>>n;
    int a[n+1];
    for(int i=0;i<n+1;i++){
        cin>>a[i];
    }
    int ans = findDuplicate(a,n);
    cout<<"Duplicate element is: "<<ans;
}
7
4 5 1 2 4 3 6 7
Duplicate element is: 4

JAVA 프로그램

import java.util.Scanner;

class Main{ 
    static int findDuplicate(int a[],int n){
        int X=0,Y=0;
        for(int i=1;i<=n;i++){
            X = X^i;
        }
        for(int i=0;i<=n;i++){
            Y = Y^a[i];
        }
        return X^Y;
    }

  public static void main(String[] args) { 
  Scanner sc = new Scanner(System.in);
    int n;
    n = sc.nextInt();	
  int a[] = new int[n+1]; 
  for(int i=0;i<n+1;i++){
      a[i] = sc.nextInt();
  }
    System.out.println("Duplicate element is: "+findDuplicate(a,n)); 
  } 
}
6
3 4 2 1 6 6 5
Duplicate element is: 6

참조

Translate »