题解 | #合并两个有序的数组#
合并两个有序的数组
https://www.nowcoder.com/practice/89865d4375634fc484f3a24b7fe65665
方法:双指针
从数组A、B的最后一个元素开始遍历,比较大小根据规则填充到A数组中。
时间复杂度:o(n)
空间复杂度:o(1)
class Solution { public: void merge(int A[], int m, int B[], int n) { int i = m - 1; int j = n - 1; int idx = m + n - 1; while (i >= 0 && j >= 0) { if (A[i] > B[j]) A[idx--] = A[i--]; else A[idx--] = B[j--]; } // 剩余元素直接填充 if (i >= 0) { while (idx >= 0) A[idx--] = A[i--]; } if (j >= 0) { while (idx >= 0) A[idx--] = B[j--]; } } };
刷题题解(c++) 文章被收录于专栏
算法题题解(c++)