[数据结构与算法]Java剑指offer3 ：查找数组中重复的数字

?关注公众号：Pyhon大视界，专注于Java和python，大数据开发。

Java 剑指Offer 3

题解：

统计一个数组中重复的数字，已知数组中所有的数值介于0到n-1之间，可以尝试将第i个元素放到第i个位置，那么，假如 i 位置已经有数值了，那么，我们就知道已经重复了。如下图所展示的，逐次遍历。

替换法（O(n),O(1)）

? ? 数组存放原则：numbers[i] = i

? ? 遍历数组所有元素，交换不符合数组存放原则的元素：

? ? ? ? 例如[2,3,1,0,2]

? ? ? ? 遍历0位元素2：（交换0位元素2和2位元素1）->[1,3,2,0,2]

? ? ? ? 遍历0位元素1：（交换0位元素1和1位元素3）->[3,1,2,0,2]

? ? ? ? 遍历0位元素3：（交换0位元素3和3位元素0）->[0,1,2,3,2]

? ? ? ? 依次遍历0、1、2、3位置元素，都符合存放原则numbers[i] = i，不做任何操作。

? ? ? ? 遍历末位元素2，此时末位元素2和2位元素2相等，出现了两次，即数字2位重复元素。

package JavaOffer;
/*
 #3  数组中重复的数字
两个方法实现，本质是一样的，按照题目的要求，时间复杂度和空间复杂度，


 */
public class JavaOffer3 {
    public static void main(String[] args) {
        JavaOffer3 jo3 = new JavaOffer3();
        int[] nums = {4, 3, 1, 1, 2, 5};
         int num =jo3.solution2(nums);
        System.out.println( num);

    }

    public int duplicate(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            while (nums[i] != i) {//依次遍历
                //如果 i  位置的值和num【i】的值相等，则说明重复，
                if (nums[i] == nums[nums[i]]) {
                    return nums[i];
                }
                //交换 i位置的值和num【i】的值
                swap(nums, i, nums[i]);
            }
            swap(nums, i, nums[i]);
        }
        return -1;
    }

    private void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }

    public int solution2 (int[] numbers) {
        if(numbers.length==0){
            return -1;
        }
        int[] arr = new int[numbers.length];
        arr[0]=-1;
        //逐次遍历数组，如果i位置的值等于number【i】的值，则返回数值
        //否则，将i处的值加入到新数组，然后比较
        for(int i=0;i<numbers.length;i++){
            if(arr[numbers[i]]==numbers[i]){
                return numbers[i];
            }
            //System.out.println(arr[i]);
            arr[numbers[i]] = numbers[i];
        }
        return -1;
    }

    public int solution3(int a[]){
        for (int i = 0; i <a.length ; i++) {
            for (int j = i+1; j <a.length ; j++) {
                if (a[i]==a[j]){
                    return a[i];
                }

            }
        }


        return -1;
    }

}

运行结果如下：

返回重复的数字，

上面方法需要不断交换数组的位置，我们定义一个新数组，存储数据，方便计算，如solution2所展示的。

如果没有时间复杂度和空间复杂度的考虑，直接可以采用遍历的方法求重复的数字。如solution3所展示的，