Leecode热题100-287.寻找重复数

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。

你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

示例 1：

输入：nums = [1,3,4,2,2]
输出：2

示例 2：

输入：nums = [3,1,3,4,2]
输出：3

示例 3 :

输入：nums = [3,3,3,3,3]
输出：3

class Solution {public static int findDuplicate(int[] nums) {/**如果没有数或者只有一个数不可能重复*/if(nums == null || nums.length <= 1) {return -1;}/**遍历每个位置使用下标连环怼进行解题*/int index = 0;/*** 如果只有n+1个数，而且数字都是1~n* 如果都不重复排完序之后数字i应该在i-1下标的问题* 遍历数组找到第一个位置不对的值*/for(int i = 0; i < nums.length; i++) {if(nums[i] != i + 1) {/*** 当前数是nums[i]，它的正确位置是nums[i]-1，如果这个位置本来就是nums[i]* 那就破案了，nums[i]至少有两个*/if(nums[nums[i]-1] == nums[i]) {return nums[i];}/*** 否则的话把nums[i]-1位置和i位置交换交换* 应为现在的i位置的数是换过来的，我们需要继续看看这个i位置是不是i+1,for循环每次都是++的，所以这里--一下*/swap(nums, i, nums[i]-1);i--;}}return -1;}private static void swap(int[] nums, int i, int j) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}
}