2种方式解决剑指offer第3题:找出数组中重复的数字。

今天来刷一道题,一道 1337 上的简单题.

找出数组中重复的数字。在一个长度为 n 的数组 nums 里的所有数字都在 0 ～ n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof

这题很简单, 就是找出数组中的随便哪一个重复数字就行了. 我们用不同的方式来提交, 看看到底不同方法的性能差异有多大.

Stream 解法

先写这个, 是因为,我们熟悉啊. 关于重复数字什么的,最近解过太多次了. 不熟悉的可以看这篇.  

计字符串中的每种字符的个数

J K L，公众号：K字的研究如何正确统计字符串里每种字符的个数-你不一定知道的Java基础知识

1. 先装箱成 Integer,
2. 然后 group by+count
3. 最后循环找到第一个搞定

class Solution {
  public int findRepeatNumber(int[] nums) {
    var map = Arrays.stream(nums).boxed()
        .collect(Collectors.groupingBy(Function.identity(),
            Collectors.counting()));
    int i = map.entrySet().stream()
        .filter(e -> e.getValue() > 1)
        .findFirst()
        .map(Map.Entry::getKey)
        .get()
        .intValue();
    return i;
  }
}

现实非常骨感

执行用时：22 ms , 在所有 Java 提交中击败了 5.08% 的用户
内存消耗：48 MB , 在所有 Java 提交中击败了 17.83% 的用户

看来, 这个玩法有点坑啊.去掉 Stream 试试看

For 解法

和上面的写法一模一样, 只是不再使用 Stream 语法

class Solution {
  public int findRepeatNumber(int[] nums) {
    HashMap<Integer, Integer> map = new HashMap<>();
    for (int num : nums) {
      Integer integer = num;
      map.merge(integer, 1, Integer::sum);
    }

    int i = 0;
    for (Map.Entry<Integer, Integer> e : map.entrySet()) {
      if (e.getValue() > 1) {
        i = e.getKey();
        break;
      }
    }
    return i;
  }
}

结果:

执行用时：10 ms , 在所有 Java 提交中击败了 10.14% 的用户
内存消耗：46.6 MB , 在所有 Java 提交中击败了 47.80% 的用户

时间快了一倍,内存没啥大变化. 看来主要是 Map 的问题,比较占地方啊.接下来优化掉 Map 试试看.

自己写 Hash 函数来做

这里, 如果要实现一个 Hash 函数的话,对于y=f(x)来看,

• 输入空间是[0,n),
• 输出空间也是[0,n)

1 比 1 的空间话, 实现起来其实很简单.用y=x当哈希函数即可.这种情况, 甚至连 key 都不用存. 只需要保持一个 value 的数组就行.

class Solution {
  public int findRepeatNumber(int[] nums) {
    int[] map = new int[nums.length];
    for (int num : nums) {
      map[num] += 1;
    }

    int i;
    for (i = 0; i < map.length; i++) {
      if (map[i] > 1) {
        break;
      }
    }
    return i;
  }
}

额, 好像什么都没写?

是的呢. 这里看起来是一个int[],但是他其实是个特殊的hash表.

java.util.Map只是collections系列框架的一个接口,你不实现他, 一样可以是一个哈希表,是个 Map.比如前面我们熟悉的ThreadLocalMap,他也是个 Map. 只是不是java.util.Map. 

ThreadLocalMap以ThreadLocal对象做key,他有一个十分优秀的哈希函数.

J K L，公众号：K字的研究ThreadLocal.hashCode有多厉害

结果:

执行用时：
1 ms , 在所有 Java 提交中击败了 80.34% 的用户
内存消耗：45.5 MB , 在所有 Java 提交中击败了 98.87% 的用户

欧耶,开始走上正路了..不过前面 1 毫秒,还有 20%人压着,好可怕. 确实让人不甘心, 继续优化.

提前返回优化

这 3 种实现其实是一种方法, 只是具体点有一些差异.

这种方法有一个问题, 他统计了所有数字的出现次数. 但是我们只是随便要一个重复的.不限制第几个.

1. 不需要全部的重复数字
2. 不需要重复数字的出现次数

那么, map 里,只要发现当前数字出现过,次数>0 就可以返回了.

class Solution {
  public int findRepeatNumber(int[] nums) {
    int[] map = new int[nums.length];
    for (int num : nums) {
      if (map[num] > 0) return num;
      map[num] += 1;
    }
    return -1;
  }
}

结果:

执行用时：1 ms , 在所有 Java 提交中击败了 80.34% 的用户
内存消耗：45.7 MB , 在所有 Java 提交中击败了 96.68% 的用户

非常尴尬, 我自作聪明去掉了一个循环,加上优化..时间没快,内存还多了.

BitSet 解法

自己写的 Hash 表,毕竟还是让人不放心. 还是用官方的数据结构试试.这里用 BitSet 来处理是否出现过.

class Solution {
  public int findRepeatNumber(int[] nums) {
    BitSet bitSet = new BitSet(nums.length);
    for (int i = 0; i < nums.length; i++) {
      int num = nums[i];
      if (bitSet.get(num)) return num;
      bitSet.set(num);
    }
    return 0;
  }
}

结果尴尬上天了.

执行用时：4 ms , 在所有 Java 提交中击败了 52.80% 的用户
内存消耗：45.8 MB , 在所有 Java 提交中击败了 95.04% 的用户

看来这个写法已经到极限了. 接下来换另一个写法

前面都是使用了额外空间,保持了原数组不动. 接下来,我们换改变原数组的方法.

排序优先

先对数组排序, 然后从前往后判断,当前数字是否和下一个相同.出现相邻元素相同, 那肯定是重复数.

class Solution {
  public int findRepeatNumber(int[] nums) {
    Arrays.sort(nums);
    for (int i = 0; i < nums.length - 1; ++i) {
      if (nums[i] == nums[i + 1]) {
        return nums[i];
      }
    }
    return 0;
  }
}

结果似乎不是很理想,或许不应该先排序.

执行用时：2 ms , 在所有 Java 提交中击败了 64.92% 的用户
内存消耗：45.7 MB , 在所有 Java 提交中击败了 96.77% 的用户

Hash 表法

刚刚我们提到, 自己实现了一个哈希表. 那么, 扩展思路,输入的nums本身,也可以当做一个哈希表. 而且是一个错位的 hash 表.

我们可以根据元素的值, 直接把他放到正确的位置上去. 如果发现正确的位置上已经有一个自己了, 那么这个元素就是重复的.

接下来按照这个描述,来实现算法.

class Solution {
  public int findRepeatNumber(int[] nums) {
    int n = nums.length;
    for (int i = 0; i < n; ++i) {
      int num = nums[i];
      if (num == i) continue;
      if (num == nums[num]) {
        return num;
      }
      nums[i] = nums[num];
      nums[num] = num;
      --i;
    }
    return 0;
  }
}

执行用时：
0 ms , 在所有 Java 提交中击败了 100.00% 的用户
内存消耗：46.1 MB , 在所有 Java 提交中击败了 68.67% 的用户

终于, 时间上去了.内存掉的好厉害. 这里前面部分都好理解, 就是最后的--i. 这里是因为i发生了交换,这里是新的未检查过的元素.所以要重新检查,要把 i++给减回来.一直检查到i位置放的是i为止.

优化内存

时间估计不能再优化了. 主要看一下内存怎么优化. 这里的内存估计是大量的 if 带来的坑. 先来优化掉内部的 if.

这个算法, 每一轮,都至少要把一个 N 放到 nums[N]的位置, 所以这个算法最多就是运行 次就可以算出结果. 这边的--i, 相当于当前循环又多跑了一次.如果下一次还是位置不对,那么这里还会继续跑下去. 其实这里是一个循环.. 那么可以用 while 替换掉这个if. 和上面是等价的.

class Solution {
  public int findRepeatNumber(int[] nums) {
    for (int i = 0; i < nums.length; ++i) {
      while (i != nums[i]) {
        int num = nums[i];
        if (num != nums[num]) {
          nums[i] = nums[num];
          nums[num] = num;
        } else {
          return nums[num];
        }
      }
    }
    return 0;
  }
}

执行结果

执行用时：0 ms , 在所有 Java 提交中击败了 100.00% 的用户
内存消耗：45.9 MB , 在所有 Java 提交中击败了 86.23% 的用户

好像也没少用多少. 自古时空两难权.就这样吧.

这里面最难理解的部分, 估计是根据数字来确定他的位置部分. 只要能理解到 Hash 表的本质, 相信看懂还是可以的.

不过呢, 是不是感觉少了点什么? 图呢, 老 K 咋可能不画图.

图示

因为这个场景动图没有意义, 最主要的是次序. 所以, 采取静态展开.

对于一个[6,4,3,0,2,1,0]这样的输入,运行状态展开是这样的.

1. 获取第 0 个元素, 得到 6
2. 把 6 放到第 6 个位置,取出当前值 0
3. 把 0 放回 0 位
4. 继续检查 0 位置, 发现是放的是 0,继续下一个数
5. 获取第一个数 4,把 4 放到第四个位置, 取出 4 位置的 2
6. 2 放回 2 位置,取出 2 位置的 3 放到 1 位.
7. 将 3 放回 3 位置, 取出 3 位的 0 放到 1 位.
8. 取出 1 位的 0, 试图把他放到 0 位,发现 0 位已经是 0 了.. 说明 0 重复 流程完毕.

有没有发现. 这个手法,其实类似于一个不使用比较的排序? 如果没有重复元素的话,最后其实会得到一个有序数组. 好了, 今天字数很够,就不扩展了.