腾讯三面：缺失的QQ号码是哪个？
The following article is from 涛歌依旧 Author 点击关注👉👉
来源丨涛歌依旧（ID：ai_taogeyijiu_2021）
今天，我们来看一道有趣的腾讯三面的面试题，有一定难度和技巧。可以坦白地说，如果没有提前进行类似训练，那就不太可能现场做对这道题目，一起来看看：
腾讯题目：假设QQ号码的取值范围是(0, max_unsigned_int)，现有n个QQ号码，求出其中缺失的最小的QQ号码。要求时间复杂度为O(n)，空间复杂度为O(1).
熟悉LeetCode的朋友自然眼前一亮，这道题是咱们的老熟人啊，一起来看看LeetCode上的题目，并以LeetCode题目为例，详细讲解具体的思路和解法。
LeetCode题目: 给定一个整数数组，请找出其中缺失的最小的正整数，要求时间复杂度为O(n)，空间复杂度为O(1)，输入输出的具体示例如下面表格所示：
| 输入数组a | 输出 |
| [1, 2, 0] | 3 |
| [3, 4, 1, -1] | 2 |
| [6, 7, 8, 12] | 1 |
我们先来分析一下:
假设a中的n个元素占满了1~n, 那么缺失的最小正整数就是n+1.
假设a中的n个元素没有完全占满1~n, 那么缺失的最小正整数必然是1~n之间的某个数。
综合可知：缺失的最小正整数必然在区间[1, n+1]中。这是一个非常重要的结论。
一. 暴力破解
暴力算法很简单，直接遍历区间[1, n+1]，然后判断元素是否在a中。此时，时间复杂度是O(n*n)，空间复杂度为O(1).
显然，无法通过面试。
二. 哈希算法
三. 巧妙标记
我们参考哈希算法，并在标记元素是否存在时做巧妙优化。
原始数组 | [3, 4, 1, -1] |
| 非正数改为n+1 | [3, 4, 1, 5] |
| 3存在，用a[3-1]的负号来标识 | [3, 4, -1, 5] |
| 4存在，用a[4-1]的负号来标识 | [3, 4, -1, -5] |
| 1存在，用a[1-1]的负号来标识 | [-3, 4, -1, -5] |
| a[x-1]=4，是正数，故x必然不存在 | x=2便是缺失的最小正整数 |
可以看到，在记录元素x是否存在时，使用的是a[x - 1]的符号，其中，x的区间是[1, n]. 该算法的时间复杂度是O(n)，空间复杂度是O(1).
package mainimport "fmt"
func abs(x int) int { if x < 0 { return -x }
return x}
func solution(a []int) int { n := len(a) for i := 0; i < n; i++ { if a[i] <= 0 { a[i] = n + 1 } }
for i := 0; i < n; i++ { num := abs(a[i]) if num <= n { a[num - 1] = -abs(a[num - 1]) } }
for i := 0; i < n; i++ { if a[i] > 0 { return i + 1 } }
return n + 1}
func main() { a := []int{3, 4, 1, -1} fmt.Println(solution(a))}四. 置换归位
我们再看看更加直观的想法。对于数组a的元素i，如果i在区间[1, n]中，可通过置换归位，把i放到a[i-1]处，如下：
输入数组a | 置换目标 |
| [1, 2, 0] | [1, 2, 0] |
| [3, 4, 1, -1] | [1, -1, 3, 4] |
| [6, 7, 8, 12] | [6, 7, 8, 12] |
置换目标 | x(缺失的最小正整数) |
| [1, 2, 0] | 3 |
| [1, -1, 3, 4] | 2 |
| [6, 7, 8, 12] | 1 |
package mainimport "fmt"
func solution(a []int) int { n := len(a) for i := 0; i < n; i++ { // 注意：下面这里要用for, 而不是if. for a[i] > 0 && a[i] <= n && a[a[i]-1] != a[i] { a[a[i]-1], a[i] = a[i], a[a[i]-1] } }
for i := 0; i < n; i++ { if a[i] != i + 1 { return i + 1 } }
return n + 1}
func main() { a := []int{3, 4, 1, -1} fmt.Println(solution(a))}结果为2，刚好就是缺失的最小正整数
<END>
【轻薄款上架】 🕚
推荐阅读：
每日打卡赢积分兑换书籍入口