# 题 1
88. 合并两个有序数组
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
示例 1：
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。
示例 2：
输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并 [1] 和 [] 。
合并结果是 [1] 。
示例 3：
输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]
解释：需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。
提示：
nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
-109 <= nums1[i], nums2[j] <= 109
进阶：你可以设计实现一个时间复杂度为 O(m + n) 的算法解决此问题吗？
题解
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
int i = m - 1; // Pointer for nums1
int j = n - 1; // Pointer for nums2
int k = m + n - 1; // Pointer for merged array (nums1)
while (i >= 0 && j >= 0) {
if (nums1[i] >= nums2[j]) {
nums1[k] = nums1[i];
i--;
} else {
nums1[k] = nums2[j];
j--;
}
k--;
}
// If there are remaining elements in nums2, copy them to nums1
while (j >= 0) {
nums1[k] = nums2[j];
j--;
k--;
}
}
# 题 2
27. 移除元素
简单
相关标签
相关企业
提示
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
说明:
为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}
示例 1：
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。
示例 2：
输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,3,0,4]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。
提示：
0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100
题解
int removeElement(int* nums, int numsSize, int val) {
int j = 0,k = 0;
for(int i=0;i<numsSize;i++){
if(nums[j] != val){
nums[k] = nums[j];
k++;
}
j++;
}
return k;
}
# 题 3
26. 删除有序数组中的重复项
给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：
更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
返回 k 。
判题标准:
系统会用下面的代码来测试你的题解:
int[] nums = [...]; // 输入数组
int[] expectedNums = [...]; // 长度正确的期望答案
int k = removeDuplicates(nums); // 调用
assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
assert nums[i] == expectedNums[i];
}
如果所有断言都通过，那么您的题解将被 通过。
示例 1：
输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
示例 2：
输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
提示：
1 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104
nums 已按 非严格递增 排列
题解
int removeDuplicates(int* nums, int numsSize) {
if (numsSize == 0) {
return 0; // 数组为空，直接返回 0
}
int j = 0; // 指向新数组的指针
for (int k = 1; k < numsSize; k++) {
if (nums[j] != nums[k]) {
j++; // 新数组长度加 1
nums[j] = nums[k]; // 复制不同的元素到新数组
}
}
return j + 1; // 返回新数组的长度
}
# 题 4
80. 删除有序数组中的重复项 II
已解答
中等
相关标签
相关企业
给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
说明：
为什么返回数值是整数，但输出的答案是数组呢？
请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}
示例 1：
输入：nums = [1,1,1,2,2,3]
输出：5, nums = [1,1,2,2,3]
解释：函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3。 不需要考虑数组中超出新长度后面的元素。
示例 2：
输入：nums = [0,0,1,1,1,1,2,3,3]
输出：7, nums = [0,0,1,1,2,3,3]
解释：函数应返回新长度 length = 7, 并且原数组的前七个元素被修改为 0, 0, 1, 1, 2, 3, 3。不需要考虑数组中超出新长度后面的元素。
提示：
1 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104
nums 已按升序排列
题解
int removeDuplicates(int* nums, int numsSize) {
if (numsSize == 0) {
return 0;
}
int k = 0;
for (int i = 0; i < numsSize; i++) {
if (k < 2 || nums[i] != nums[k - 1] || nums[i] != nums[k - 2]) {
nums[k] = nums[i];
k++;
}
}
return k;
}
以上均为双指针题目，关键为移动指针进行比较
# 题 4
169. 多数元素
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1：
输入：nums = [3,2,3]
输出：3
示例 2：
输入：nums = [2,2,1,1,1,2,2]
输出：2
提示：
n == nums.length
1 <= n <= 5 * 104
-109 <= nums[i] <= 109
# 解析
为了解决这个问题，我们可以使用 Boyer-Moore 投票算法。该算法的核心思想是通过不断消除不同的元素对来找到多数元素。
以下是解决方案的步骤：
初始化两个变量：candidate 和 count，分别表示候选元素和其出现次数。
遍历数组，对于每个元素：
如果 count 为 0，则将当前元素设为候选元素。
如果当前元素等于候选元素，则递增 count。
否则，递减 count。
最终的候选元素就是多数元素。
直观理解,对于本题由于多数元素是大于一半,因此将不同元素两两配对消除,最后一定会剩下多数元素,因此,多数元素的count大于0,此时candidate即为结果
题解
int majorityElement(int* nums, int numsSize) {
int candidate = nums[0],count = 0;
for(int i=0;i<numsSize;i++){
if(candidate == nums[i]){
count++;
}else{
count--;
if(count == 0){
candidate = nums[i+1];
}
}
}
return candidate;
}
# 拓展
该算法还可以求
1/k的元素：
假设我们要找到数组中出现次数超过n/k的元素。
我们可以维护一个大小为k-1的候选元素数组 cands 和一个对应的计数数组 cnts，初始时都为空。
遍历数组中的每个元素：
如果 cands 中已经有这个元素，就将对应的计数 cnts 加1。
否则，如果 cands 的大小小于k-1，就将当前元素加入 cands 和 cnts。
否则，将 cnts 中的所有计数减1。如果某个计数变为0，就从 cands 和 cnts 中移除对应的元素。
最后，我们需要检查 cands 中的每个元素是否真正出现次数超过n/k。
排名问题：
假设我们要找到数组中第k大或第k小的元素。
我们可以使用类似的思路，维护一个大小为k的候选元素数组 cands 和一个对应的计数数组 cnts。
遍历数组中的每个元素：
如果 cands 中已经有这个元素，就将对应的计数 cnts 加1。
否则，如果 cands 的大小小于k，就将当前元素加入 cands 和 cnts。
否则，将 cnts 中的所有计数减1。如果某个计数变为0，就从 cands 和 cnts 中移除对应的元素。
最后，cands 中的第k个元素就是我们要找的结果。
# 题 5
189. 轮转数组
提示
给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
示例 1:
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]
示例 2:
输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释:
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]
提示：
1 <= nums.length <= 105
-231 <= nums[i] <= 231 - 1
0 <= k <= 105
进阶：
尽可能想出更多的解决方案，至少有 三种 不同的方法可以解决这个问题。
你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？
# 解析
暴力求解：
最直接的方法是将数组的后 k 个元素“剪切”到数组的前面。
首先，我们申请一个长度为 k 的额外存储空间，用来存储“剪切”的部分。
然后，将数组的后 k 个元素复制到这个额外的存储空间中。
接下来，将数组中的前 n-k 个元素向右移动 k 个位置。
最后，将额外存储空间中的元素复制回数组的前面。
时间复杂度：O(n)，空间复杂度：O(k)。
利用题目中的信息，我们可以知道每个元素在原来位置的基础上向右移动 k % n 个位置。
我们可以通过循环单方面交换 x 与 (x + k) % n 位置处的元素进行更新。
每更新一个元素，计数器 count 加一，直到所有元素都被更新。
时间复杂度：O(n)，空间复杂度：O(1)。
首先，反转整个数组，将数组中的元素顺序颠倒，这样原来在末尾的元素会移到数组的开头。
然后，反转前 k 个元素，将前 k 个元素逆序排列，这样原来在前面的 k 个元素会移到数组的末尾。
最后，反转剩余的元素，将剩余的元素逆序排列，这样原来在中间的元素会在原位置上。
时间复杂度：O(n)，空间复杂度：O(1)。
题解
void rotate(int* nums, int numsSize, int k) {
k = k % numsSize; // 防止 k > n 越界
int count = 0; // 记录已经交换的元素个数
for (int start = 0; count < numsSize; start++) {
int current = start;
int prev = nums[start];
do {
int next = (current + k) % numsSize;
int temp = nums[next];
nums[next] = prev;
prev = temp;
current = next;
count++;
} while (start != current);
}
}
# 感悟
对于上述问题,除了暴力开辟一个新空间的方法,一开始使用原地算法简单的将current-k再判断是否小于0在数组长度为偶数时会出现循环位移的错误,而正确解法为取模操作从而避免在数组长度为偶数时出现循环的问题.当然本题最简单的方法还是反转数组法,将前k个数与之后的数反转,再分别反转两段数即可.
