给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列。
注意:最终,合并后数组不应由函数返回,而是存储在数组 nums1 中。为了应对这种情况,nums1 的初始长度为 m + n,其中前 m 个元素表示应合并的元素,后 n 个元素为 0 ,应忽略。nums2 的长度为 n 。
输入:nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出:[1,2,2,3,5,6]
解释:需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ,其中斜体加粗标注的为 nums1 中的元素。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/merge-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
上面这道题是力扣88题,是美团的面试题,一共让写两道题,这是第二道。
本来想就在数组nums1当中修改的,不申请额外的空间。
1.比nums1[i]小的,就先把nums[i+1:]里的数存nums[i:],然后nums1[i]放nums2[j]。
2.比nums1所有数都大的,直接放在nums1后面,然后退出
3.考虑另外的情况,nums1=[4],nums2=[1,3,5,6],这个要求注意外层循环,和插入nums2[j]后,nums1的i又该怎么取值的问题。
外层循环就只考虑j<n,每次插入一个数,就让nums1的下标=0
4.ac的时候遇见nums1=[0],nums2=[1],就输出了nums1=[0,1],这就有问题了啊,nums1应该是个空数组,输出是[1],而给的nums1有数,就需要对nums1的长度进行判断
让循环条件多一个i<temp(temp的初始值=n,但是每次插入一个数,temp+1)
如果i=0,temp = n=0,就不用进入循环了,所以在循环外还需要将nums2的数全部给nums1
具体就是
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
i,j =0,0
temp = m
while j<n and i<temp:
if nums1[i]>=nums2[j]:
nums1[i+1:] = nums1[i:temp]
nums1[i] = nums2[j]
j+=1
i=0
temp+=1
elif i>=temp-1:
nums1[i+1:] = nums2[j:]
break
else:
i+=1
nums1[temp:] = nums2[j:]
然后又去看了在力扣上的解法,好家伙,直接申请额外的空间,最后将结果给nums1,这就简单多了!!!!
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
"""
Do not return anything, modify nums1 in-place instead.
"""
re = []
j=0
i = 0
while i<m or j<n:
if i==m:
re.append(nums2[j])
j += 1
elif j==n:
re.append(nums1[i])
i += 1
elif nums1[i]<=nums2[j]:
re.append(nums1[i])
i += 1
else:
re.append(nums2[j])
j += 1
nums1[:] = re
结果内存消耗是一样的,但是申请额外的空间的做法比直接在nums1上改的快,啊
给我的感觉就是乐扣上中等及简单题可以多做,面试的题目就这样,也不难…………啊