Leetcode 第88题 合并两个有序数组

给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中*，*使 nums1 成为一个有序数组。

说明:

• 初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。
• 你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。

示例:

输入: nums1 = [1,2,3,0,0,0], m = 3 nums2 = [2,5,6], n = 3

输出: [1,2,2,3,5,6]

解题思路

思路一:直接把 nums2 的 数 复制 到 nums1 ,然后用排序算法 进行排序,排序算法使用希尔排序。

思路二.定义双指针,指向2个数组不是 0 的末尾,然后谁大 就把 值 填充到 nums1 的末尾,然后再移动指针,如此反复循环。

合并 + 排序

pub fn merge(nums1: &mut Vec<i32>, m: i32, nums2: &mut Vec<i32>, n: i32) {
    let mut pointer_a = 0 ;
    let mut pointer_b = 0;

    for i in m as usize..nums1.len(){
        nums1[i] = nums2[pointer_b];
        pointer_b += 1;
    }
    pointer_b = m as usize;
    shell(nums1);
}
//希尔排序
fn shell<T: Ord + Copy>(a: &mut [T]) {
    let n = a.len();
    let mut h = 1;
    while h < n / 3 {
        h = h * 3 + 1;
    }
    while h >= 1 {
        for i in h..n {
            let tmp = a[i];
            let mut j = i;

            while tmp < a[j - h] {
                a[j] = a[j - h];
                j -= h;
                if let None = j.checked_sub(h) {
                    break;
                }
            }
            a[j] = tmp;
        }
        h /= 3;
    }
}
fn main() {
    let mut a = vec![1,2,3,0,0,0];
    let mut b = vec![2,5,6];
    merge(a.as_mut(), 3, b.as_mut(), 3);
    println!("Hello, world! {:?}",a);
}

时间复杂度：O(n+log_n)

空间复杂度：O(1)

双指针 从后面

​

pub fn merge(nums1: &mut Vec<i32>, m: i32, nums2: &mut Vec<i32>, n: i32) {
    let mut i = m - 1;
    let mut j = n - 1;
    let mut k = m + n - 1;
		
    while i >= 0 && j >= 0 {
        if nums1[i as usize] > nums2[j as usize] {
            nums1[k as usize] = nums1[i as usize];
            k -= 1;
            i -= 1;
        } else {
            nums1[k as usize] = nums2[j as usize];
            k -= 1;
            j -= 1;
        }
    }

    while j >= 0 {
        nums1[k as usize] = nums2[j as usize];
        k -= 1;
        j -= 1;
    }
}