leetcode/
merge_sorted_array.rs

1//! # 88. 合并两个有序数组
2//!
3//! 难度 简单
4//!
5//! 给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
6//!
7//!
8//!
9//! ## 说明：
10//!
11//! - 初始化 *nums1* 和 *nums2* 的元素数量分别为 *m* 和 *n* 。
12//! - 你可以假设 *nums1* 有足够的空间（空间大小大于或等于 *m + n*）来保存 *nums2* 中的元素。
13//!
14//!
15//! ## 示例：
16//!
17//! ```text
18//! 输入：
19//! nums1 = [1,2,3,0,0,0], m = 3
20//! nums2 = [2,5,6],       n = 3
21//!
22//! 输出：[1,2,2,3,5,6]
23//! ```
24//!
25//!
26//! ## 提示：
27//!
28//! - `-10^9 <= nums1[i], nums2[i] <= 10^9`
29//! - `nums1.length == m + n`
30//! - `nums2.length == n`
31//!
32//! See [leetcode](https://leetcode-cn.com/problems/merge-sorted-array/)
33
34pub struct Solution;
35
36impl Solution {
37    pub fn merge(nums1: &mut Vec<i32>, m: i32, nums2: &mut Vec<i32>, n: i32) {
38        assert_eq!(nums1.len(), (m + n) as usize);
39        assert_eq!(nums2.len(), n as usize);
40
41        let mut p = (nums1.len() - 1) as i32;
42        let mut p1 = m - 1;
43        let mut p2 = n - 1;
44
45        while p1 >= 0 && p2 >= 0 {
46            if nums1[p1 as usize] >= nums2[p2 as usize] {
47                nums1[p as usize] = nums1[p1 as usize];
48                p1 -= 1;
49            } else {
50                nums1[p as usize] = nums2[p2 as usize];
51                p2 -= 1;
52            }
53
54            p -= 1;
55        }
56
57        let rest = (p2 + 1) as usize;
58        let _ = &mut nums1[..rest].copy_from_slice(&nums2[..rest]);
59    }
60}
61
62#[cfg(test)]
63mod tests {
64    use super::*;
65
66    #[test]
67    fn test() {
68        let cases: Vec<(Vec<i32>, (Vec<i32>, i32, Vec<i32>, i32))> = vec![
69            // (vec![1,2,2,3,5,6], (vec![1,2,3,0,0,0], 3, vec![2,5,6], 3)),
70            (vec![1,2,2,3,5,6], (vec![2,5,6,0,0,0], 3, vec![1,2,3], 3)),
71            // (vec![1], (vec![0], 0, vec![1], 1)),
72        ];
73
74        for (expect, (mut nums1, m, mut nums2, n)) in cases {
75            Solution::merge(&mut nums1, m, &mut nums2, n);
76            assert_eq!(expect, nums1);
77        }
78    }
79}
leetcode/merge_sorted_array.rs

leetcode/
merge_sorted_array.rs
