og

双指针:合并两个有序数组 (88)

Snipaste_20200703_160643.jpg 给定两个有序整数数组 nums1 和 nums2,将 nums2 合并到 nums1 中,使得 num1 成为一个有序数组。
说明:

  • 初始化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]

注意:此题是就地修改,切片是重新复制,所以不能使用

        
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
//js /** * @param {number[]} nums1 * @param {number} m * @param {number[]} nums2 * @param {number} n * @return {void} Do not return anything, modify nums1 in-place instead. */ var merge = function(nums1, m, nums2, n) { let index1=m-1 let index2=n-1 let indexMerge=m+n-1 while(index1>=0 || index2>=0){ if (nums1[index1]>nums2[index2]) { nums1[indexMerge--]=nums1[index1--] } if (nums1[index1]<=nums2[index2]) { nums1[indexMerge--]=nums2[index2--] } if (index1<0) { nums1[indexMerge--]=nums2[index2--] } if (index2<0){ nums1[indexMerge--]=nums1[index1--] } } };

思路:确定三个指针,1数组指针,2数组指针 ,合并后的数组指针,都由尾部开始遍历,取1数组的数与2数组两两比较,较大的数排到末尾

思路图

Article at   2020/07/06 13:30  Published  code  Category,viewed  152  times

Relevant tags:    算法 

Address:   https://www.kedong.me/article/25

Copyright Notice: Freely reproduced for non-commercial use