招商门户网站建设方案,网站建设中 html,vi设计,徐州h5建站模板合并两个有序数组 文章目录归并思路二归并 核心思路#xff1a; 依次比较#xff0c;取较小值放入新数组中 i 遍历nums1 #xff0c; j 遍历nums2 #xff0c;取较小值放入nums3中 那如果nums[i] 和nums[j]中相等#xff0c;随便放一个到nums3 那如果nums[i] 和nums[j]中相…合并两个有序数组 文章目录归并思路二归并 核心思路 依次比较取较小值放入新数组中 i 遍历nums1 j 遍历nums2 取较小值放入nums3中 那如果nums[i] 和nums[j]中相等随便放一个到nums3 那如果nums[i] 和nums[j]中相等随便放一个到nums3 此时 nums1 中的元素已经走完了那么直接把 nums2 中剩下的元素拿到 nums3 中去, 因为nums2 是有序数组 所以不需要考虑 nums2剩下的元素比nums3小 这总方法最大的问题就是新开辟了一个数组 如果题目要求空间复杂度为O(1) 这种方法就不管用了
思路二 归并依次比较取较小值 ,但是思路二是依次比较取较大值 思路二和归并大体上相似 , 思路二整体思路 i 指向nums1最后一个有效元素 ,向前遍历 j 指向nums2最后一个有效元素 向前遍历 dst指向nums1 的最后一个元素 ,也是向前遍历 j 指向的元素如果大于 i 指向的元素那么就把 j 指向的元素放入 dst 指向的位置中去 当j 向前遍历完nums2时 我们直接让它结束就行了 但是还需要多考虑一种情况 当nums1中的每一个元素都比nums2中的每一个元素大 nums1 一定会先遍历完 这时候就需要将nums2 的每一个元素提前放入nums1中 void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{int i m -1 ;int j n- 1 ;int dst m n -1 ;while( i 0 j 0){//nums2先走完 , j 0 if( nums1[i] nums2[j]) //取较大值{nums1[dst] nums1[i];dst-- ;i--;}else{nums1[dst]nums2[j];dst--;j--;}}// nums1 先走完 , i 0 while( j0 ){nums1[dst] nums2[j];j -- ;dst -- ;}
}如果你觉得这篇文章对你有帮助不妨动动手指给点赞收藏加转发给鄃鳕一个大大的关注 你们的每一次支持都将转化为我前进的动力
