88.合并两个有序数组

链接：88.合并两个有序数组
难度：Easy
标签：数组、双指针、排序
简介：给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。

题解 1 - typescript

• 编辑时间：2021-04-05
• 执行用时：72ms
• 内存消耗：39.4MB
• 编程语言：typescript
• 解法介绍：从后往前遍历，节省空间。

function merge(nums1: number[], m: number, nums2: number[], n: number): void {
  if (m === 0) {
    nums1.length = 0;
    nums1.push(...nums2);
  } else if (n === 0) {
  } else {
    let lPos = m - 1;
    let rPos = n - 1;
    let curPos = m + n - 1;
    while (curPos >= 0) {
      const num1 = nums1[lPos];
      const num2 = nums2[rPos];
      let curNum = num1;
      if (lPos < 0) {
        rPos--;
        curNum = num2;
      } else if (rPos < 0) {
        lPos--;
      } else if (num1 >= num2) {
        lPos--;
      } else {
        rPos--;
        curNum = num2;
      }
      nums1[curPos--] = curNum;
    }
  }
}

题解 2 - c

• 编辑时间：2021-11-30
• 执行用时：4ms
• 内存消耗：5.9MB
• 编程语言：c
• 解法介绍：从后往前遍历。

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
    int i = m + n - 1, i1 = m - 1, i2 = n - 1;
    while (i >= 0 && i1 >= 0 && i2 >= 0) {
        if (nums1[i1] >= nums2[i2]) nums1[i--] = nums1[i1--];
        else nums1[i--] = nums2[i2--];
    }
    if (i1 < 0 && i2 >= 0) while(i >= 0) nums1[i--] = nums2[i2--];
}

题解 3 - c

• 编辑时间：2021-11-30
• 执行用时：20ms
• 内存消耗：8.7MB
• 编程语言：c
• 解法介绍：排序。

int comp(const void *a, const void *b) {
    return *(int *)a - *(int *)b;
}
bool containsDuplicate(int* nums, int numsSize){
    qsort(nums, numsSize, sizeof(int), comp);
    int f = 0;
    for (int i = 1; i < numsSize; i++) {
        if (nums[i - 1] == nums[i]) {
            f = 1;
            break;
        }
    }
    return f;
}

题解 4 - cpp

• 编辑时间：2021-12-21
• 内存消耗：8.7MB
• 编程语言：cpp
• 解法介绍：从后往前遍历。

class Solution {
   public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int idx = m + n - 1, idx1 = m - 1, idx2 = n - 1;
        while (idx1 >= 0 || idx2 >= 0) {
            if (idx1 >= 0 && (idx2 < 0 || nums1[idx1] >= nums2[idx2])) {
                nums1[idx--] = nums1[idx1--];
            } else {
                nums1[idx--] = nums2[idx2--];
            }
        }
    }
};

题解 5 - cpp

• 编辑时间：2023-08-13
• 内存消耗：8.77MB
• 编程语言：cpp
• 解法介绍：双指针遍历。

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        for (int idx = nums1.size() - 1, i1 = m - 1, i2 = n - 1; idx >= 0; idx--) {
            if (i2 < 0 || i1 >= 0 && nums1[i1] > nums2[i2]) {
                nums1[idx] = nums1[i1--];
            } else {
                nums1[idx] = nums2[i2--];
            }
        }
    }
};

题解 6 - python

• 编辑时间：2023-08-13
• 执行用时：44ms
• 内存消耗：15.68MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        i1 = m-1
        i2 = n-1
        for idx in range(len(nums1) - 1, -1, -1):
            if i2 < 0 or i1 >= 0 and nums1[i1] > nums2[i2]:
                nums1[idx] = nums1[i1]
                i1 -= 1
            else:
                nums1[idx] = nums2[i2]
                i2 -= 1

题解 7 - rust

• 编辑时间：2023-08-13
• 内存消耗：2.09MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn merge(nums1: &mut Vec<i32>, m: i32, nums2: &mut Vec<i32>, n: i32) {
        let m = m as usize;
        let n = n as usize;
        let mut i1 = m - 1;
        let mut i2 = n - 1;
        for idx in (0..nums1.len()).rev() {
            if i2 >= n || i1 < m && nums1[i1] > nums2[i2] {
                nums1[idx] = nums1[i1];
                i1 -= 1;
            } else {
                nums1[idx] = nums2[i2];
                i2 -= 1;
            }
        }
    }
}