面试题03. 数组中重复的数字

题目来源

LEETCODE

题目描述

题目分析

哈希计数

空间换时间,比map要快

   /*
   2 <= n <= 100000
        */
   public static int findRepeatNumber(int[] nums) {
        int ans = -1;
        int[] arr = new int[100001];
       for (int i: nums) {
           if (arr[i] == 1){
               return i;
           }
           arr[i]++;
       }
        return ans;
   }

使用hash表

   public static int findRepeatNumber(int[] nums) {
       Map<Integer, Integer> map = new HashMap<>();
       for (int i: nums) {
           if (map.containsKey(i)){
               return i;
           }

           map.put(i, 1);
       }

       return -1;
   }

使用set

利用set集合不能重复的特点，遍历数组添加到集合，当add添加set集合中已有的元素时候返回false，以此作为判断是否有重复元素的条件

   public static int findRepeatNumber(int[] nums) {
       Set<Integer> set = new HashSet<>();
       for (int i: nums) {
           if (set.contains(i)){
               return i;
           }

           set.add(i);
       }

       return -1;
   }

时间复杂度：O(n)O(n)。
遍历数组一遍。使用哈希集合（HashSet），添加元素的时间复杂度为 O(1)O(1)，故总的时间复杂度是 O(n)O(n)。
空间复杂度：O(n)O(n)。不重复的每个元素都可能存入集合，因此占用 O(n)O(n) 额外空间。

原地交换

   public static int findRepeatNumber(int[] nums) {
       int i = 0;
       while (i < nums.length){
           if (i == nums[i]){ // 这个抽屉里面的数据已经放好了
               i++;
           }else if (i < nums[i]){  // 索引 < 索引出的值： 将索引处的值放到它应该在的位置
               int o = nums[i];
               if (nums[i] == o){  // 如果交换的过程中发生了重复
                   return o; // 直接返回
               }
               nums[i] = nums[o];
               nums[o] = o;
           }else{  // i 之前的数据一定时排序好的。如果本次遇到的数num[i] < i, 说明重复了
               return nums[i];
           }
       }
       return -1;
   }

如果没有重复数字，那么正常排序后，数字i应该在下标为i的位置，所以思路是重头扫描数组，遇到下标为i的数字如果不是i的话，（假设为m),那么我们就拿与下标m的数字交换。在交换过程中，如果有重复的数字发生，那么终止返回ture