LeetCode 面试题 17.19 – 消失的两个数字

题目链接:LeetCode 面试题 17.19 – 消失的两个数字

这个题还蛮有意思的,题目限定了时间复杂度要$O(n)$,空间复杂度要$O(1)$,主要是空间限制。

对于$O(n)$的时间复杂度很容易想到哈希表,可是这需要额外的空间,即空间复杂度也是$O(n)$的。如何在不增加额外空间的前提下建立哈希表呢?我们知道所有的数都小$3\times 10^4$,所以只需要在原数组上打标记就可以了,即读到一个实际值为$x$的数字,就在$x$的下标的那个数字上加上一个大于$3\times 10^4$的数字,或者把一个用不到的二进制位置$1$。

说点什么

avatar
  Subscribe  
提醒