题解 | #数组中重复的数字#

参考：

    //解题思路
    /*替换法（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位重复元素
     */
    public int duplicate (int[] numbers) {
        for (int i = 0; i < numbers.length; i++) {
            if (numbers[i] != i){
                if (numbers[i] == numbers[numbers[i]]) return numbers[i];
                int temp = numbers[numbers[i]];
                numbers[numbers[i]] = numbers[i];
                numbers[i] = temp;
                i--;//遍历完0位元素以及交换完数字后，如果0位元素仍不符合数组存放原则：numbers[i] = i，那么还要重新遍历0位元素
            }
        }
        return -1;
    }

自己写的：

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param numbers int整型一维数组 
     * @return int整型
     */
    public int duplicate (int[] numbers) {
        // write code here
        int[] count_numbers = new int[numbers.length];
        for(int i = 0; i < count_numbers.length; i++){
            count_numbers[i] = 0;
        }
        for(int i = 0; i < numbers.length; i++){
            count_numbers[numbers[i]] = count_numbers[numbers[i]] + 1;
            if (count_numbers[numbers[i]] == 2){
                return numbers[i];
            }
        }
        return -1;
    }
}