Java数组中重复的数字（java数组重组）

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

package com.hy.algorithms;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * 利用Set集合，遍历数组的元素，检查元素是否在集合中，不在则插入到集合里面；
 * 否则表明当前元素在数组中重复，返回当前元素。
 * 
 * @author 红鱼程序生活
 *
 */
public class FindSameNum {

	public static void main(String[] args) {
		Integer[] arr = {0,2,3,1,5,4,1,3};
		int result = duplicate(arr);
		System.out.println(Arrays.asList(arr) + "数组重复的数字是：" + result);
	}

	private static int duplicate(Integer[] arr) {
		Set<Integer> s = new HashSet<>();
		for (int i = 0; i < arr.length; i++) {
			if (s.contains(arr[i])) {
				return arr[i];
			} else {
				s.add(arr[i]);
			}
		}
		return -1;
	}
}

上面是的代码时间复杂度O(N)和空间复杂度O(N)， 关于如何计算这两个维度，可以查看下一篇文章介绍，还有其他处理方式空间复杂度为O(1)，也将在下一篇文章中介绍。