今日题目有：
- 合并两个有序数组
- 移除元素
- 删除有序数组中的重复项
合并两个有序数组
题目描述
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
示例：
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
思路
-
常规思路：双指针，一个指针遍历数组1，一个指针遍历数组2，都是从前往后遍历，谁数值小进新数组。 当其中一个指针拨到数组末尾时结束循环。剩余没遍历完的数组直接add到新数组。 返回新数组即是结果。
-
利用好数组1初始长度是 m + n，依然是双指针，但从后往前遍历，每次大的元素放在数组1的末尾。
这样相当于数组1是基础数组，遍历数组2，把元素放在数组1的合适的位置即可。
Swift实现
class Solution {
func merge(_ nums1: inout [Int], _ m: Int, _ nums2: [Int], _ n: Int) {
var i = m - 1, j = n - 1, cur = m + n - 1
while j >= 0{
if nums1[i] > nums2[j] && i >= 0{
nums1[cur] = nums1[i]
i -= 1
} else {
nums1[cur] = nums2[j]
j -= 1
}
cur -= 1
}
}
}
移除元素
题目描述
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。
假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：
更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。 返回 k。
示例：
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
思路
遍历数组，找到不等于val的数，依次排放即可。
Swift实现
class Solution {
func removeElement(_ nums: inout [Int], _ val: Int) -> Int {
var cur = 0
for num in nums {
if num != val {
nums[cur] = num
cur += 1
}
}
return cur
}
}
删除有序数组中的重复项
题目描述
给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
示例：
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
思路
参考灵茶山爱府老师的栈思路， 感觉这种问题很好解。
本质是考虑nums[statckSize - k]（栈底数）和nums[cur]（栈顶数）是不是相等，不相等即满足条件，入栈，栈size+1，继续遍历。
Swift实现
class Solution {
func removeDuplicates(_ nums: inout [Int]) -> Int {
var cur = 2
let n = nums.count
guard n >= 2 else { return n }
for idx in 2..<n {
if nums[idx] != nums[cur - 2] {
nums[cur] = nums[idx]
cur += 1
}
}
return cur
}
}
...