查找重复元素


难度级别 中等
经常问 Apple 彭博 谷歌 微软
排列 二进制搜索 两指针

给定一个 排列 如果n的大小为n + 1,且该数组的每个元素在1到n(含)之间,则该数组中有一个重复元素,找到重复元素。

蛮力法–查找重复元素的方法1

对于每个第ith个元素,在给定数组上从(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:遍历数组,并更新哈希图中每个元素的频率。

步骤:遍历哈希图,并返回频率为2的元素。

查找重复元素的复杂度分析

空间复杂度:O(n),我们在for哈希中使用了额外的内存,在最坏的情况下,其大小为n。

时间复杂度: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到n的异或并将其存储在变量X中。

步骤:找到给定数组的xor并将其存储在变量Y中。

步骤:求X和Y的异或值以找到重复元素。

查找重复元素的复杂度分析

空间复杂度: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

參考資料