数组中重复的数字

题目描述:

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的,但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如,如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出是第一个重复的数字2。


解法

1.排序法

对数组进行排序后,判断相邻两个元素是否相等,相等则返回

public boolean duplicate(int numbers[],int length,int [] duplication) {
        //判断特殊情况
        if(length==0){
            duplication[0] = -1;
            return false;
        }
        //排序
        Arrays.sort(numbers);
        //查找排序后的数组的相邻位置是否存在相同元素,存在则返回
        for(int i=0;i<length-1;i++){
            if(numbers[i]==numbers[i+1]){
                duplication[0] = numbers[i];
                return true;
            }
        }
        duplication[0] = -1;
        return false;
    }
}

时间复杂度:O(nlogn)
空间复杂度:O(1)

2.利用HashSet辅助完成

新建一个HashSet,循环数组进行判断:
1)若HashSet中不存在当前元素,则将当前元素加到HashSet中
2)若HashSet中存在当前元素,则说明当前元素为重复元素

public class Solution {
    // Parameters:
    //    numbers:     an array of integers
    //    length:      the length of array numbers
    //    duplication: (Output) the duplicated number in the array number,length of duplication array is 1,so using duplication[0] = ? in implementation;
    //                  Here duplication like pointor in C/C++, duplication[0] equal *duplication in C/C++
    //    这里要特别注意~返回任意重复的一个,赋值duplication[0]
    // Return value:       true if the input is valid, and there are some duplications in the array number
    //                     otherwise false
    public boolean duplicate(int numbers[],int length,int [] duplication) {
        //判断特殊情况
        if(length==0){
            duplication[0] = -1;
            return false;
        }
        //新建一个HashSet作为辅助
        HashSet<Integer> hs = new HashSet<Integer>();
        //循环数组进行判断:若HashSet中不存在当前元素,将当前元素添加到HashSet中;若存在,说明当前元素就是重复元素
        for(int num:numbers){
            if(!hs.contains(num)){
                hs.add(num);
            }
            else{
                duplication[0] = num;
                return true;
            }
        }
        duplication[0] = -1;
        return false;
    }
}

时间复杂度:O(n)
空间复杂度:O(n)

3.根据特性

数组的长度为 n 且所有数字都在 0 到 n-1 的范围内,我们可以将每次遇到的数进行"归位",当某个数发现自己的"位置"被相同的数占了,则出现重复

public class Solution {
    // Parameters:
    //    numbers:     an array of integers
    //    length:      the length of array numbers
    //    duplication: (Output) the duplicated number in the array number,length of duplication array is 1,so using duplication[0] = ? in implementation;
    //                  Here duplication like pointor in C/C++, duplication[0] equal *duplication in C/C++
    //    这里要特别注意~返回任意重复的一个,赋值duplication[0]
    // Return value:       true if the input is valid, and there are some duplications in the array number
    //                     otherwise false
    public boolean duplicate(int numbers[],int length,int [] duplication) {
        //判断特殊情况
        if(length==0){
            duplication[0] = -1;
            return false;
        }
        for(int i=0;i<length;i++){
            while(i!=numbers[i]){
                if(numbers[i] == numbers[numbers[i]]){
                    duplication[0] = numbers[i];
                    return true;
                }
                else{
                    int tmp = numbers[i];
                    numbers[i] = numbers[tmp];
                    numbers[tmp] = tmp;
                }
            }
        }
        duplication[0] = -1;
        return false;
    }
}

时间复杂度:O(n)
空间复杂度:O(1)

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容