88. Merge Sorted Array Easy

1/**
2 * [88] Merge Sorted Array
3 *
4 * You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.
5 * Merge nums1 and nums2 into a single array sorted in non-decreasing order.
6 * The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.
7 *  
8 * Example 1:
9 *
10 * Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
11 * Output: [1,2,2,3,5,6]
12 * Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
13 * The result of the merge is [<u>1</u>,<u>2</u>,2,<u>3</u>,5,6] with the underlined elements coming from nums1.
14 *
15 * Example 2:
16 *
17 * Input: nums1 = [1], m = 1, nums2 = [], n = 0
18 * Output: [1]
19 * Explanation: The arrays we are merging are [1] and [].
20 * The result of the merge is [1].
21 *
22 * Example 3:
23 *
24 * Input: nums1 = [0], m = 0, nums2 = [1], n = 1
25 * Output: [1]
26 * Explanation: The arrays we are merging are [] and [1].
27 * The result of the merge is [1].
28 * Note that because m = 0, there are no elements in nums1. The 0 is only there to ensure the merge result can fit in nums1.
29 *
30 *  
31 * Constraints:
32 *
33 * nums1.length == m + n
34 * nums2.length == n
35 * 0 <= m, n <= 200
36 * 1 <= m + n <= 200
37 * -10^9 <= nums1[i], nums2[j] <= 10^9
38 *
39 *  
40 * Follow up: Can you come up with an algorithm that runs in O(m + n) time?
41 *
42 */
43pub struct Solution {}
44
45// problem: https://leetcode.com/problems/merge-sorted-array/
46// discuss: https://leetcode.com/problems/merge-sorted-array/discuss/?currentPage=1&orderBy=most_votes&query=
47
48// submission codes start here
49
50impl Solution {
51    pub fn merge(nums1: &mut Vec<i32>, m: i32, nums2: &mut Vec<i32>, n: i32) {
52        let mut i = m + n - 1;
53        let (mut x, mut y) = (m - 1, n - 1);
54
55        while i >= 0 {
56            let n = if x < 0 {
57                y -= 1;
58                nums2[(y + 1) as usize]
59            } else if y < 0 {
60                x -= 1;
61                nums1[(x + 1) as usize]
62            } else {
63                if nums1[x as usize] > nums2[y as usize] {
64                    x -= 1;
65                    nums1[(x + 1) as usize]
66                } else {
67                    y -= 1;
68                    nums2[(y + 1) as usize]
69                }
70            };
71            nums1[i as usize] = n;
72            i -= 1;
73        }
74    }
75}
76
77// submission codes end
78
79#[cfg(test)]
80mod tests {
81    use super::*;
82
83    #[test]
84    fn test_88() {
85        let mut nums1 = vec![1,2,3,0,0,0];
86        let mut nums2 = vec![2,5,6];
87        Solution::merge(&mut nums1, 3, &mut nums2, 3);
88        assert_eq!(nums1, vec![1,2,2,3,5,6]);
89    }
90}
91