剑指offer之数组中重复的数字

题目描述

题解一题解二题解三

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

数据范围：0≤n≤10000
进阶：时间复杂度O(n)，空间复杂度O(n)

解题思路：定义一个新的数组a[n]，遍历所给的数组numbers，当遍历到第i个元素时，将a[numbers[i]]++，这样遍历完一遍numbers后，遍历a[n]，如果a[n]中有元素大于1，说明有重复数字，返回大于1时的值就是重复的数字。

import java.util.*;


public class Solution {
    
    public int duplicate (int[] numbers) {
        // write code here
        int[] a = new int[numbers.length];
        for(int i = 0; i < numbers.length; i++){
            a[numbers[i]]++;
            if(a[numbers[i]] > 1){
                return numbers[i];
            }
        }
        return -1;
    }
}

时间复杂度：O（n） 空间复杂度 ：O（n）

他人解题思路：对于这种数组元素在 [0, n-1] 范围内的问题，可以将值为 i 的元素调整到第 i 个位置上进行求解。本题要求找出重复的数字，因此在调整过程中，如果第 i 位置上已经有一个值为 i 的元素，就可以知道 i 值重复。

import java.util.*;


public class Solution {
    
    public int duplicate (int[] numbers) {
        // write code here
        if(numbers.length==0){
            return -1;
        }
        for(int i = 0; i < numbers.length; i++){
        	//如果numbers[i] == i，什么也不做，进入下一个循环
            if(numbers[i] != i){
            	//如果numbers[i] == numbers[numbers[i]]，说明第i个位置上已经有numbers[i]了，返回numbers[i]即可
            	//否则交换numbers[i]和numbers[numbers[i]]
                if(numbers[i] == numbers[numbers[i]])
                    return numbers[i];
                int temp = numbers[numbers[i]];
                numbers[numbers[i]] = numbers[i];
                numbers[i] = temp;
                //!!!遍历完0位元素以及交换完数字后，如果0位元素仍不符合数组存放原则：numbers[i] = i，那么还要重新遍历0位元素,如果不i--，有个特例过不了，比如[2,0,3,1,4,4]
                i--;
            }
        }
        return -1;
    }
}

时间复杂度：O（n） 空间复杂度 ：O（1）

他人解题思路：直接使用java的set特性来实现

import java.util.*;

public class Solution {
    
    public int duplicate (int[] numbers) {
        HashSet set = new HashSet<>();
        for (int i = 0; i < numbers.length; i++) {
            if (!set.add(numbers[i])) {
                return numbers[i];
            }
        }
        return -1;
    }
}

时间复杂度：O（n） 空间复杂度 ：O（n）