难度

简单

思路

暴力遍历

  • 使用 HashSet 集合存储遍历对象。
  • 获取一个元素，先使用 contain() 判断 HashSet 是否包含该元素，如果包含，则直接 Return，否则 i++。
    1. public static int findRepeatNumber_0(int[] nums) {
    2.   if (nums.length == 0)
    3.       return -1;
    4.   // 构建HashSet集合
    5.   Set<Integer> resultMap = new HashSet<Integer>();
    6.   for (int i = 0; i < nums.length; i++) {
    7.       if (resultMap.contains(nums[i])) {
    8.           return nums[i];
    9.       } 
    10.       resultMap.add(nums[i]);
    11.   }
    12.   return -1;
    13. }
    | 时间复杂度 | O(n) | | —- | —- | | 空间复杂度 | O(n) |

对号入座法

  • 前提: 数组长度为 n 且数字都在 0~n-1 范围内。因此，可以让它们对号入座（数组值与数组序号相对应）。
  • 如果在对号入座的过程中，发送座位号的数值相同，则表示重复。相当于买票看电影，但前提是座位号与票号是一致的，即对号入座。
    1. public static int findRepeatNumber_3(int[] nums) {
    2.   if (nums.length == 0)
    3.       return -1;
    4.   for (int i = 0; i < nums.length; i++) {
    5.       // 一直循环
    6.       while (nums[i] != i) {
    7.           if (nums[i] != nums[nums[i]]) {
    8.               // 交换
    9.               int temp = nums[nums[i]];
    10.               nums[nums[i]] = nums[i];
    11.               nums[i] = temp;
    12.           } else {
    13.               // 遇到相等数据，直接返回
    14.               return nums[i];
    15.           }
    16.       }
    17.   }
    18.   return -1;
    19. }
    | 时间复杂度 | O(n) | | —- | —- | | 空间复杂度 | O(1) |

总结

虽然是 简单 类型，但是需要让大家注意 时间 和 空间 两种概念。比如使用 HashSet 时间复杂度较低（查找判断为 O(1)），但是空间复杂度高。而使用 “对号入座” 方法，前提条件比较苛刻，它让空间复杂度变为 O(1)。