주어진 정렬 배열의 각 요소가 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
