一、搜索插入位置
简单
给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
示例 1 ：
输入：nums = [2,2,1]
输出：1
示例 2 ：
输入：nums = [4,1,2,1,2]
输出：4
示例 3 ：
输入：nums = [1]
输出：1
提示：
1 <= nums.length <= 3 * 10^4-3 * 10^4 <= nums[i] <= 3 * 10^4- 除了某个元素只出现一次以外，其余每个元素均出现两次。
1.1 异或^
异或运算 a ⊕ a = 0，我们可以用异或来消除所有重复出现的元素，最后剩下的一定是只出现一次的元素。
a ⊕ b = b ⊕ a
(a ⊕ b) ⊕ c = a ⊕ (b ⊕ c)
❓直接初始化ans = 0会不会影响结果
- 如果唯一出现的元素是0，那么异或完所有数字后结果仍然为0，不影响
- 如果唯一出现的元素不是0，0可以看成任意两个重复的数字异或出来的结果，也不影响
class Solution {
public int singleNumber(int[] nums) {
int ans = 0;
for(int num: nums) ans ^= num;
return ans;
}
}二、多数元素
简单
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1：
输入：nums = [3,2,3]
输出：3示例 2：
输入：nums = [2,2,1,1,1,2,2]
输出：2提示：
n == nums.length1 <= n <= 5 * 10^4-10^9 <= nums[i] <= 10^9- 输入保证数组中一定有一个多数元素。
进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
2.1 严格众数
目标元素在数组中出现次数 大于 ⌊ n/2 ⌋ ，说明其他元素加起来的次数一定小于⌊ n/2 ⌋
任意两个不一样的元素一比一消去，消去后剩下的数就是目标数
就像竞选投票一样，现在有很多个竞选人，nums[i] = 111表示给第111位竞选者投了一票，现在我们要找出得票最多的人
轮流唱票，在最终的两个人对决之中，你我各得一票 等于 我们俩个人都不得票，从中任意选取一个人为临时胜出者即可
由于是严格众数，所以最终获胜的竞选人的票数一定会压其他人一头
class Solution {
public int majorityElement(int[] nums) {
int ans = 0;
int ticket = 0;
for (int n : nums) {
if (ticket == 0) { // 你我各得一票 等于 我们俩个人都不得票
ans = n; // 选取当前竞选者为临时胜出者
ticket = 1; // 重新开始计票
} else ticket += n == ans ? 1 : -1; // 投的是同一个人，加一票，否则扣一票
}
return ans;
}
}三、颜色分类
中等
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地↗ 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库内置的 sort 函数的情况下解决这个问题。
示例 1：
输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]示例 2：
输入：nums = [2,0,1]
输出：[0,1,2]提示：
n == nums.length1 <= n <= 300nums[i]为0、1或2
进阶：
- 你能想出一个仅使用常数空间的一趟扫描算法吗？
3.1 两次双指针
用l)指针保护已经归位的数字，用r指针寻找需要归位的数字
- 第一趟
r不断向右找0，找到了就换到l指针处，交给其保护 - 将
r拉回到l指针位置 - 第二趟
r不断向右找1，并把他们放到左边
class Solution {
public void sortColors(int[] nums) {
int l = 0, r = 0;
// 处理0
while (r < nums.length) {
// r指针向右找0
while (r < nums.length && nums[r] != 0) r++;
if (r == nums.length) break;
// 找到0了把他换到左边，并移动左边界保护已处理的0
int tmp = nums[l];
nums[l] = nums[r];
nums[r] = tmp;
l++;
r++;
}
r = l; // 拉回到左指针
// 处理1
while (r < nums.length) {
// r指针向右找1
while (r < nums.length && nums[r] != 1) r++;
if (r == nums.length) break;
// 找到1了把他换到左边，并移动左边界保护已处理的0和1
int tmp = nums[l];
nums[l] = nums[r];
nums[r] = tmp;
l++;
r++;
}
}
}3.2 一次双指针
- 对于一个已经有序的颜色分类数组，如果要插入一个新的颜色
- 插入2，直接在数组末尾插入
- 插入1，在1的末尾和2的开头插入（等价于把第一个2变为1，然后在末尾插一个2）
- 插入0，在0的末尾和1的开头插入（等价于把第一个1变为0，把第一个2变为1，然后在末尾插一个2）
- 遍历到第
i个元素时，相当于：对于一个已经有序的颜色分类数组 [0, i - 1]，插入一个新的颜色nums[i] - 从1的结果来看，无论
nums[i]（新插入的颜色）是什么，都有一个共同的操作：插一个2在i处（即：有序数组 [0, i - 1]的末尾）
- 所以我们先记录
nums[i]的值为x，然后直接把他设为2 - 然后判断
x是否为1，如果为1，把第一个2变为1 - 然后判断
x是否为0，如果为0，把第一个2变为1，把第一个1变为0
用l)保护已经处理完的0，用r)保护已经处理完的1和0，2个指针分割三个区域
[0, l)都为0，[l, r)都为1，[r, nums.length)都为2
class Solution {
public void sortColors(int[] nums) {
int l = 0, r = 0;
for (int i = 0; i < nums.length; i++) {
int t = nums[i];
nums[i] = 2;
if (t <= 1) {
nums[r++] = 1;
}
if (t == 0) {
nums[l++] = 0;
}
}
}
}对于nums = [1, 0, 2, 1, 2, 0, 2, 1, 2, 2, 0]
nums = [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]，先全变成2nums = [1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2]，再变成1nums = [1, 0, 2, 1, 2, 0, 2, 1, 2, 2, 0]，然后变成0
num[i] = 2在所有循环内都会执行，所以从结果看是先全变成2，然后nums[p1]=1在所有<=1的情况下都会执行，所以从结果看是2中部分替换为1，同理0就是在2的1中部分替换为0
四、下一个排列
中等
整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。
- 例如，
arr = [1,2,3]，以下这些都可以视作arr的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1]。
整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。
- 例如，
arr = [1,2,3]的下一个排列是[1,3,2]。 - 类似地，
arr = [2,3,1]的下一个排列是[3,1,2]。 - 而
arr = [3,2,1]的下一个排列是[1,2,3]，因为[3,2,1]不存在一个字典序更大的排列。
给你一个整数数组 nums ，找出 nums 的下一个排列。
必须 原地 ↗修改，只允许使用额外常数空间。
示例 1：
输入：nums = [1,2,3]
输出：[1,3,2]示例 2：
输入：nums = [3,2,1]
输出：[1,2,3]示例 3：
输入：nums = [1,1,5]
输出：[1,5,1]提示：
1 <= nums.length <= 1000 <= nums[i] <= 100
4.1 移动山谷
对于nums = [3, 1, 2, 4]，横看成岭侧成峰，把它想象成一座山，人站在最右侧的山峰上从右往左看
人 人
| |
| | ===> | |
| | | | | |
| | | | | | | |
3 1 2 4 3 1 4 2类比满十进1，当前位置数字为9，数字 变大 后，需要把当前位置数字重置为最小0，即 9 + 1 = 1 0
从小到大找，找到第一个变小的地方，再从小到大找一个比他大的数对换
即找到第一个
nums[l] < nums[l + 1]，对于8397521
- 这是唯一能“变大”的位置，即 8 3 97521
- 因为
[l + 1 … nums.length)是降序，即 83 97521
即找到
r满足nums[r] > nums[l]，交换nums[l]和nums[r]后，数字会 变大，即8 5 97 3 21
- 因为
l右边是降序，所以翻转[l+1, nums.length)后就变成升序，这样子就是下一个排列：85 12379
class Solution {
public void nextPermutation(int[] nums) {
int length = nums.length;
// 从右向左找到第一个下降的位置
int l = length - 2;
while (l >= 0 && nums[l] >= nums[l + 1]) l--;
// 找到了下降的位置
if (l >= 0) {
// 从右向左找到第一个比 nums[l] 大的数
int r = length - 1;
while (r >= 0 && nums[r] <= nums[l]) r--;
// 交换 nums[l] 和 nums[r]
swap(nums, l, r);
}
// 反转 l+1 到末尾的部分
reverse(nums, l + 1, length - 1);
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
private void reverse(int[] nums, int start, int end) {
while (start < end) {
swap(nums, start, end);
start++;
end--;
}
}
}五、寻找重复数
中等
给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。
你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。
示例 1：
输入：nums = [1,3,4,2,2]
输出：2示例 2：
输入：nums = [3,1,3,4,2]
输出：3示例 3 :
输入：nums = [3,3,3,3,3]
输出：3 提示：
1 <= n <= 10^5nums.length == n + 11 <= nums[i] <= nnums中 只有一个整数 出现 两次或多次 ，其余整数均只出现 一次
进阶：
- 如何证明
nums中至少存在一个重复的数字? - 你可以设计一个线性级时间复杂度
O(n)的解决方案吗？
5.1 快慢指针
给定一个包含
n + 1个整数的数组nums，其数字都在[1, n]范围内（包括1和n），可知至少存在一个重复的整数
题中这句话说明了nums数组的构成为：
- 1到n的所有整数各一个
- 随机一个重复的数字
- 数字随机打乱
把nums[i]当成指针，从下标为0开始，nums[nums[i]]将会无重复地遍历完数组的每个元素（因为1到n的所有整数各一个）
但是由于唯一重复元素的存在，所以这个数组存在一个环，遍历入环后会在环中循环遍历
👉解法参考：环形链表 II↗
class Solution {
public int findDuplicate(int[] nums) {
int slow = 0, fast = 0;
while (true) {
slow = nums[slow];
fast = nums[nums[fast]];
if (slow == fast) break;
}
int head = 0;
while (head != slow) {
head = nums[head];
slow = nums[slow];
}
return slow;
}
}