算法:合并两个有序数组

这道题的核心思想利用数组已经有序的特点采用“从后往前填充”的贪心思想每次选择当前最大的元素放到合并数组的最后位置。因为nums1后面有预留空间如果从前往后合并会导致原来的元素被覆盖需要不断移动数据。因此选择逆向遍历从nums1和nums2的最后一个有效元素开始比较当前两个元素中较大的那个一定应该放在合并数组的最后空位放入后继续向前比较剩余元素直到所有元素都移动到正确位置。本质上就是利用有序数组的性质每次确定当前最大值的位置通过双指针从尾部向前构造最终有序数组。这种方法避免了额外空间也避免了元素移动所以能够在O(mn) 时间复杂度、O(1) 空间复杂度下完成合并。void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) { int im-1; int jn-1; int kmn-1; while(i0j0) { if(nums1[i]nums2[j]) { nums1[k--]nums1[i--]; } else { nums1[k--]nums2[j--]; } } while(i0) { nums1[k--]nums1[i--]; } while(j0) { nums1[k--]nums2[j--]; } }