数据结构

• 面试题3：数组中重复的数字
  在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。例如，如果输入长度为 7 的数组 {2, 3, 1, 0, 2, 5, 3}，那么对应的输出是第一个重复的数字 2。
  思考：
  题目给的限定条件不能浪费，注意以下条件
  1.在一个长度为n的数组里，所有数都在0~n-1之间
  2.找出任意的一个

public static int duplicate(int[] nums) {
        int length = nums.length;
        // 增加鲁棒性，如果数组为空或者长度为0
        if (nums == null || length <= 0)
            return -1;
        // 控制外部循环
        for (int i = 0; i < length; i++) {
            // 如果key和value不想等，而且value为索引的对应的值也不相等的话
            // 第二个条件是因为当找到相同数字时也是和索引不一样
            while (nums[i] != i && nums[i] != nums[nums[i]]) {
                // 交换两个key为索引和 value为索引的两个数字的值
                swap(nums, i, nums[i]);
            }
            // 如果key和value的值相等，而且value的值等于以value为索引的值
            if (nums[i] != i && nums[i] == nums[nums[i]]) {
                return nums[i];
            }
        }
        return -1;
    }
    // 交换两个数字
private static void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }  

测试用例：
正常情况：长度为n的数组包含一个或者多个重复数字
正常情况：不包含重复的数字
无效的输入用例：空指针，长度为n的数组包含含有0~n-1以外的数字，长如为0的数组