剑指offer学习（Java）——面试题3.1：数组中的重复数字

灰太狼 2022-05-22 09:09 180阅读 0赞

题目：找出数组中的重复数字

在一个长度为n的数组里所有的数字都在0~n-1的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复数字。例如，输入\{2,3,1,0,2,5,3\}，输出2或者3。

假设数组中的数都在0~n-1之间

#### 解一：先排序再判断相邻数字是否相同 ####

import java.util.ArrayList;
    import java.util.Collections;
    import java.util.List;
    import java.util.Scanner;
    
    //假设第一行输入数组的长度，第二行输入数组
    public class Solution{
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            List<Integer> array = new ArrayList<>();
            int n = sc.nextInt();
            for(int i=0;i<n;i++){
                array.add(sc.nextInt());        
            }
            sc.close();
            System.out.println(duplicate(array));
        }
    
        //假定没有找到重复数字的时候返回-1
        private static int duplicate(List<Integer> array){
            if(array == null || array.size()==0){
                return -1;
            }
            Collections.sort(array);
            for(int i = 0;i<array.size()-1;i++){
                if(array.get(i)==array.get(i+1)){
                    return array.get(i);
                }
            }
            return -1;
        }
    }

运行结果

![70][]

#### 解二：用哈希表 ####

每扫描一个数字判断哈希表里是否已经有了，有就找到了重复数字，没有就把它加入哈希表

private static int duplicate(List<Integer> array){
            if(array == null || array.size()==0){
                return -1;
            }
            Set<Integer> hashset = new HashSet<>();
            for(int i : array){
                if(hashset.contains(i)){
                    return i;
                }else{
                    hashset.add(i);
                }
            }
            return -1;
        }

运行结果

![70][]

#### 解三：占位 ####

private static int duplicate(List<Integer> array){
            if(array == null || array.size()==0){
                return -1;
            }
            for(int i = 0;i<array.size();i++){
                //如果i位置上的数m等于i，说明位置是对的，下一个
                if(array.get(i)!=i){
                    //m不等于i时进入判断，若m等于m位置上的数，说明这个数重复了
                    if(array.get(i)==array.get(array.get(i))){
                        return array.get(i);
                    }else{//若m等于m位置上的数，则把m放到m位置上，即占到正确的位置上
                        int tmp = array.get(i);
                        array.set(i, array.get(array.get(i)));
                        array.set(tmp, tmp);
                    }
                }
            }
            //若每个数都占到了正确的位置上却没有发现重复的数则说明没有重复的数
            return -1;
        }

运行结果

![70][]

拓展：如何返回所有的重复数字，而不是任意一个重复数字？

（今天有点晚了，下篇写......）

[70]: /images/20220522/57e2ae54d54d44c58e50a2678dba4d0e.png