剑指 Offer 03. 数组中重复的数字

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1：
输入： [2, 3, 1, 0, 2, 5, 3] 输出：2 或 3 

  1. package com.coco.learnalgorithmone.array;
  3. import java.util.*;
  5. /**
  6.  * 剑指 Offer 03. 数组中重复的数字
  7.  * 找出数组中重复的数字。
  8.  *
  9.  *
  10.  * 在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。
  11.  * 数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。
  12.  * 请找出数组中任意一个重复的数字。
  13.  */
  14. public class FindRepeatNumber {
  16.     public static void main(String[] args) {
  17.         int[] nums = {2, 3, 1, 0, 2, 5, 3};
  18.         System.out.println(findRepeatNumber1(nums));
  19.         System.out.println(findRepeatNumber2(nums));
  20.         System.out.println(findRepeatNumber3(nums));
  21.         System.out.println(findRepeatNumber4(nums));
  22.     }
  24.     public static int findRepeatNumber1(int[] nums) {
  25.         Set<Integer> numSet = new HashSet<>();
  27.         for (int num : nums) {
  28.             if (numSet.contains(num)) {
  29.                 return num;
  30.             }
  32.             numSet.add(num);
  33.         }
  35.         return -1;
  36.     }
  38.     public static int findRepeatNumber2(int[] nums) {
  39.         Arrays.sort(nums);
  41.         for (int i = 1; i < nums.length; i++) {
  42.             if (nums[i] == nums[i - 1]) {
  43.                 return nums[i];
  44.             }
  45.         }
  47.         return -1;
  48.     }
  50.     public static int findRepeatNumber3(int[] nums) {
  51.         int[] tmp = new int[nums.length];
  53.         for (int num : nums) {
  54.             if (tmp[num] != 0) {
  55.                 return num;
  56.             }
  58.             tmp[num] = 1;
  59.         }
  61.         return -1;
  62.     }
  64.     public static int findRepeatNumber4(int[] nums) {
  65.         for (int i = 0; i < nums.length; i++) {
  66.             int num = nums[i];
  67.             if (num != i) {
  68.                 int corr = nums[num];
  69.                 if (num == corr) {
  70.                     return num;
  71.                 }
  73.                 nums[i] = corr;
  74.                 nums[num] = num;
  75.                 --i;
  76.             }
  77.         }
  79.         return -1;
  80.     }
  82. }

findRepeatNumber1

思路：利用Set集合的特性，遍历数组，往集合中新增num，当新增的num已经存在Set集合中时，代表num重复出现。

findRepeatNumber2

思路：将数组从小到大排序，遍历数组，比较相邻的两个num，当相等时，代表num重复出现。

findRepeatNumber3

思路：根据题目得知数组中num的范围在[0, n-1]区间，由此创建一个与数组长度一致的临时数组，用于记录每一个索引上num的状态。
遍历数组，往临时数组的num索引上赋值1。若临时数组的num索引上的值不为0，则代表num重复出现。