算法001

描述

在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的，也不知道每个数字重复几次。请找出数组中任意一个重复的数字。

例子

Input:
	{2, 3, 1, 0, 2, 5}
Output:
	2

思路

由于数组中的值大小 为0 到 n-1，可以通过交换就数组中的元素放到与其下标对应的位置，若有两个数要出现在同一个位置，则找到了这个数。

代码

public class Question001 {
    public static void main(String[] args) {
        int[] array = new int[] {2,3,1,0,2,5};
        for (int i = 0; i < array.length; i++) {
            while(i != array[i]) {
                if(array[i] == array[array[i]]) {
                    System.out.println(array[i]);
                    return;
                } else {
                    swap(array,i,array[i]);
                }
            }
        }
    }

    public static void swap(int[] array, int left, int right) {
        int temp = array[left];
        array[left] = array[right];
        array[right] = temp;
    }
}