前言#
准备跑路了，不过在这之前，还得培养自己的算法思维，不然等面试算法这块一定爆炸。
我这边准备跟着leetcode提供的面试经典 150 题来刷
其实每日随机一题才是最好的，因为经典150题是按照类别来分开的，所以我们可以知道使用什么方式是最适合的解法。
但由于我个人算法很差，所以我还是先跟着类别来刷好点。
不多说，直接来看题
题目#
问题：
给你两个按 非递减顺序 排列的整数数组 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
-10^9 <= nums1[i], nums2[j] <= 10^9
进阶：你可以设计实现一个时间复杂度为 O(m + n) 的算法解决此问题吗？
分析#
这道题很简单，暴力的解法俩for即可实现，不过时间复杂度为O(m * n)。
我们这里采用进阶的方案，即双指针的方式，一个指针指向数组A，另一个指针指向数组B
因为俩数组是已经排序好了的，所以我们可以从后往前遍历数组A
如果数组A的元素A[i]小于等于数组B的元素B[j]，那么这个B[j]就可以插入到A[j]前面（因为已经是排序好了的，所以插入后必定也是保持原有顺序的），然后j += 1。直到数组A遍历完了又或者数组B遍历完。
时间复杂度为O(m + n)
这里有个点需要注意，那就是可能存在剩余，比如A遍历完了，B还没遍历完，这个时候B就还有剩下的元素，那么就应该把它们放到数组A前面，因为它们必定小于数组A最小的元素。
空间复杂度，我们没有额外的消耗，只有几个常量，所以空间复杂度为O(n)
代码#
pub fn merge(nums1: &mut Vec<i32>, m: i32, nums2: &mut Vec<i32>, n: i32) {
if n <= 0 {
return;
} else if m <= 0 {
// 什么沙雕例子：[0,0,0,0,0]，m居然是0
nums1.clear();
nums1.append(nums2);
return
}
let mut i = (m - 1) as isize;
let mut j = (n - 1) as isize;
// 处理下初始情况，可能第二个数组第一个就比第一个数组最后一个大
if nums2[0] >= nums1[i as usize] {
nums1.splice(m as usize..(m + n) as usize, nums2.iter().map(|i| *i));
return;
}
// 先拿出原来的数据，这里往后面补充0是真没用
while i >= 0 && j >= 0 {
// 如果第二个数组的最后一个值大于第一个数组的最后一个值，那么就往第一个数组最后插入一个数，移除一个0，同时将n的指针往前走1步
if nums2[j as usize] >= nums1[i as usize] {
nums1.insert((i + 1) as usize, nums2[j as usize]);
nums1.pop();
j -= 1;
} else {
i -= 1;
}
}
// 最后处理下边界值，第二个数组可能会有多出来的值。
if j >= 0 {
for t in 0..=j {
nums1.pop();
nums1.insert(0, nums2[(j - t) as usize]);
}
}
}然后我们还可以编写测试用例，Rust里写大部分算法的测试用例还是很舒服的
#[cfg(test)]
mod tests {
use super::merge;
#[test]
fn test_merge() {
assert_eq!(
merge(
&mut [1, 2, 3, 0, 0, 0].to_vec(),
3,
&mut [2, 5, 6].to_vec(),
3
),
()
);
assert_eq!(merge(&mut [1].to_vec(), 1, &mut [].to_vec(), 0), ());
assert_eq!(merge(&mut [0].to_vec(), 0, &mut [2, 5, 6].to_vec(), 3), ());
assert_eq!(merge(&mut [2, 0].to_vec(), 1, &mut [1].to_vec(), 1), ());
assert_eq!(merge(&mut [0,0,0,0,0].to_vec(), 0, &mut [1,2,3,4,5].to_vec(), 5), ());
}
}然后终端直接cargo test test_merge即可
总结#
这道题还算是简单的，很容易就可以想出来双指针的方案。后面有一堆抽象的题目和解，是没有数学思维就基本想不到的那种。。。