leetcode_rust/
merge_sorted_array.rs

1#![allow(dead_code)]
2
3pub fn merge(nums1: &mut Vec<i32>, m: i32, nums2: &mut Vec<i32>, n: i32) {
4    if n == 0 {
5        return;
6    }
7    if m == 0 {
8        for (i, num) in nums2.iter().enumerate() {
9            nums1[i] = *num;
10        }
11        return;
12    }
13
14    let m = m as usize;
15    let n = n as usize;
16    // move n position distances
17    for i in (0..m).rev() {
18        nums1[i + n] = nums1[i];
19    }
20    let mut count = 0;
21    let mut i = n;
22    let mut j = 0;
23
24    while i != m + n && j != n {
25        if nums1[i] < nums2[j] {
26            nums1[count] = nums1[i];
27            i += 1;
28        } else {
29            nums1[count] = nums2[j];
30            j += 1;
31        }
32        count += 1;
33    }
34
35    while i != m + n {
36        nums1[count] = nums1[i];
37        i += 1;
38        count += 1;
39    }
40
41    while j != n {
42        nums1[count] = nums2[j];
43        j += 1;
44        count += 1;
45    }
46}
47
48// insert larger number to tail
49pub fn merge2(nums1: &mut Vec<i32>, m: i32, nums2: &mut Vec<i32>, n: i32) {
50    if n == 0 {
51        return;
52    }
53    if m == 0 {
54        for (i, num) in nums2.iter().enumerate() {
55            nums1[i] = *num;
56        }
57        return;
58    }
59    let mut k = m + n - 1;
60    let mut i = m - 1;
61    let mut j = n - 1;
62    // guard
63    while k >= 0 {
64        if (j < 0 && i >= 0) || (i >= 0 && nums1[i as usize] > nums2[j as usize]) {
65            nums1[k as usize] = nums1[i as usize];
66            i -= 1;
67            k -= 1;
68        } else if (i < 0 && j >= 0) || (j >= 0 && nums1[i as usize] <= nums2[j as usize]) {
69            nums1[k as usize] = nums2[j as usize];
70            j -= 1;
71            k -= 1;
72        }
73    }
74}
75
76#[cfg(test)]
77mod tests {
78    use super::*;
79
80    #[test]
81    fn test1() {
82        let mut nums1 = vec![1, 2, 3, 0, 0, 0];
83        let mut nums2 = vec![2, 5, 6];
84        let nums3 = vec![1, 2, 2, 3, 5, 6];
85        merge(&mut nums1, 3, &mut nums2, 3);
86        assert_eq!(nums1, nums3);
87
88        let mut nums1 = vec![1, 2, 4, 5, 6, 0];
89        let mut nums2 = vec![3];
90        let nums3 = vec![1, 2, 3, 4, 5, 6];
91        merge(&mut nums1, 5, &mut nums2, 1);
92        assert_eq!(nums1, nums3);
93    }
94
95    #[test]
96    fn test2() {
97        let mut nums1 = vec![1, 2, 3, 0, 0, 0];
98        let mut nums2 = vec![2, 5, 6];
99        let nums3 = vec![1, 2, 2, 3, 5, 6];
100        merge(&mut nums1, 3, &mut nums2, 3);
101        assert_eq!(nums1, nums3);
102
103        let mut nums1 = vec![1, 2, 4, 5, 6, 0];
104        let mut nums2 = vec![3];
105        let nums3 = vec![1, 2, 3, 4, 5, 6];
106        merge2(&mut nums1, 5, &mut nums2, 1);
107        assert_eq!(nums1, nums3);
108    }
109}
leetcode_rust/merge_sorted_array.rs

leetcode_rust/
merge_sorted_array.rs
