HOT 100 技巧题（136/169/75/31/287）

136. 只出现一次的数字

• 技巧类型题目，通过异或运算实现

169. 多数元素

• 三种常见解法：1. 哈希2. 排序3. 投票法

75. 颜色分类

1. 单指针 + 两次遍历：第一次遍历把所有0都交换到前面，记录最后一个0的位置'index'，第二次遍历从'index+1'开始，把所有1都交换到前面；
2. 双指针 + 一次遍历：记录存放0的位置'left'，存放2的位置'right'，从左向右遍历并交换，i之前的位置一定全部为0，'right'之后的位置一定全部为2，所以遍历终止条件为'i <= right'

31. 下一个排列

字典序：对于单个字符来说，通常依据其 ASCII 码值或特定字符编码规则进行排序。 例如，在 ASCII 码中，数字字符（'0' 到 '9'）、大写字母（'A' 到 'Z'）、小写字母（'a' 到 'z'）依次排列，其中数字字符的 ASCII 码值 < 大写字母 < 小写字母。

解题思路
1. 从后往前找到第一组递增的的相邻序列 nums[i] < nums[i+1];
2. 在这组相邻序列之后，找到右边第一个j，满足nums[i] < nums[j];
3. 交换nums[i], nums[j];
4. 翻转 nums.begin() + 1 + i, nums.end()。

287. 寻找重复数

解题思路
假设重复的数字为target:
1. 对于[1, target-1]中的任意一个数字i，在nums中满足nums[j] <= i的元素个数count[i]一定满足：count[i] <= i;
2. 对于[target, n]中的任意一个数字i，在nums中满足nums[j] <= i的元素个数count[i]一定满足：count[i] > i;
3. 利用二分查找的思想，如果count[mid] <= mid，则mid一定不是重复元素，且[1, mid]中的元素都不重复，继续找[mid+1, right];
4. 如果count[mid] > mid，则target一定满足target <= mid，继续找[left, mid-1];