写在前面

近期看面经, 发现有一类题常出现, 那就是寻找缺失数字, 基于这道题的变式题目也很多, 下面来总结一下.

下面总结的是缺失数字以及出现次数不同于其他数字的两大类题目.

主要用到的知识点:

1. 哈希集合: 需要占用空间, 可以考虑原地哈希, 但是不好想.
2. 排序+二分: 排序操作时间复杂度高.
3. 位运算: 这里主要指异或运算.
4. 数学方法: 找关系联立方程组, 通过求和等方式完成.
5. 特殊解法:(只能针对某道题)

缺失数字类

关于缺失数字, 有下面这几类题型:

1. 已排序, 找0~n-1中缺失的数字.剑指 Offer 53 - II. 0～n-1中缺失的数字 - 力扣（LeetCode）.
2. 已排序, 找缺失的第$k$个数字.1539. 第 k 个缺失的正整数 - 力扣（LeetCode）;
3. 未排序, 找0~n中缺失的数字,面试题 17.04. 消失的数字 - 力扣（LeetCode）;
4. 未排序, 找0~n-1中缺失的两个数字.面试题 17.19. 消失的两个数字 - 力扣（LeetCode）;
5. 未排序, 找缺失的最小正整数, 41. 缺失的第一个正数 - 力扣（LeetCode）;

出现次数类

1. 未排序, 除两个数字出现一次, 其他数字均出现两次, 找出出现一次的数字. 剑指 Offer 56 - I. 数组中数字出现的次数 - 力扣（LeetCode）;

2. 未排序, 除一个数字只出现了一次外, 其他数字均出现了三次, 找出出现一次的数字. 剑指 Offer 56 - II. 数组中数字出现的次数 II - 力扣（LeetCode）;

3. 未排序, 找出出现次数超过数组长度一半的数字. 剑指 Offer 39. 数组中出现次数超过一半的数字 - 力扣（LeetCode）;