1 /**
 2  * @author: wooch
 3  * @create: 2020/02/14
 4  */
 5 
 6 import java.util.Arrays;
 7 
 8 /**
 9  * 找出数组中重复的数字。
10  * 在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。
11  * 数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。
12  * 请找出数组中任意一个重复的数字。
13  */
14 public class P3_FindRepeatNumber {
15     public int findRepeatNumber(int[] nums) {
16         // Arrays.sort(nums);
17         // int res = -1;
18         // for (int i = 0; i < nums.length; i++) {
19         //     if (nums[i] == res) {
20         //         return res;
21         //     } else {
22         //         res = nums[i];
23         //     }
24         // }
25         // return res;
26 
27         // int len = nums.length;
28         // int[] arr = new int[len];
29         // for (int i = 0; i < len; i++) {
30         //     arr[nums[i]]++;
31         //     if (arr[nums[i]] > 1) {
32         //         return nums[i];
33         //     }
34         // }
35         // return 0;
36 
37 
38         for (int i = 0; i < nums.length; i++) {
39             while (i != nums[i]) {
40                 if (nums[i] == nums[nums[i]]) {
41                     return nums[i];
42                 } else {
43                     swap(nums, i, nums[i]);
44                 }
45 
46             }
47         }
48         return -1;
49     }
50 
51     private void swap(int[] nums, int i, int j) {
52         int temp = nums[i];
53         nums[i] = nums[j];
54         nums[j] = temp;
55     }
56 }