一、前记(2/3)
差点这个星期的blog也给咕咕了。数学强化学到积分那里好难。还好坚持下来今天搞定了(意味着高数上的内容全部搞定),晚上把我的apple pencil充上电再总结一下高数上的内容。(美滋滋!!!)专业课肝到线性表就觉得好烦,书本是使用C or C艹进行讲解的,我一个Python简直顶不住。语法什么的也太不一样了吧。不过还好,数据结构以前的呃内容都还是记得到,不难不难。
二、题目描述

u1s1,这个题如果是C来写的话,我个人觉得可能会比较麻烦,可能会创建一个新的数组外加双指针来解决问题(只是猜想,还没有具体的验证)。但是在Python里面就不用去考虑这些有的没的。
三、解题思路
1、我的思路
(Python3)
其实我的思路比较简单,因为题目说明了nums1里面有些末尾数字0是用来占位的,所以我们要把它删除。然后将nums2的数据添加到nums1的末尾。最后进行降序排序。
#encoding:utf-8
class Solution:
def merge(self, nums1, m: int, nums2, n: int) -> None:
"""
Do not return anything, modify nums1 in-place instead.
"""
for i in range(len(nums1)-1,m-1,-1):
del nums1[i]
for i in range(len(nums2)):
nums1.append(nums2[i])
return nums1.sort()
(C)
属实太巧了,在看线性表的时候刚好也看到了有序数据元素的合并,书上的题目没有这里题目难。打算现在来尝试一下。思路也还是一样,另外开辟一个线性表nums,在nums1和nums2进行双指针比较。
参考代码如下:
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
int *nums = (int *)malloc(sizeof(int) *(m + n));
int i = 0, j = 0, x = 0;
while (i < m&&j < n)
{
//当nums1和nums2的长度均小的时候
if (nums1[i] <= nums2[j])
{
nums[x] = nums1[i];
i++;
}
else {
nums[x] = nums2[j];
j++;
}
x++;
}
if (i == m && j < n) {
while (j < n) {
nums[x] = nums2[j];
j++;
x++;
}
}
if (i < m&&j == n) {
while (i < m) {
nums[x] = nums1[i];
i++;
x++;
}
}
for (i = 0; i < nums1Size; i++) {
nums1[i] = nums[i];
}
}
2、别人的思路
太有意思了,官方的解法给了一个从后往前的双指针解法,其实我个人感觉和从前往后没差。p1和p2分别指向nums1有效值的尾部和nums2的尾部,p指向nums1的尾部,当p1和p2都存在的时候,从尾部开始比较值(因为这个是有序列表),当p2所指的值大于p1所指的值,可以把当前值放到nums1的末尾,并且p2向前移动。否则末尾值等于p1所指的值,并且p1向前移动。
参考代码(官方):
class Solution(object):
def merge(self, nums1, m, nums2, n):
"""
:type nums1: List[int]
:type m: int
:type nums2: List[int]
:type n: int
:rtype: void Do not return anything, modify nums1 in-place instead.
"""
# two get pointers for nums1 and nums2
p1 = m - 1
p2 = n - 1
# set pointer for nums1
p = m + n - 1
# while there are still elements to compare
while p1 >= 0 and p2 >= 0:
if nums1[p1] < nums2[p2]:
nums1[p] = nums2[p2]
p2 -= 1
else:
nums1[p] = nums1[p1]
p1 -= 1
p -= 1
# add missing elements from nums2
nums1[:p2 + 1] = nums2[:p2 + 1]
四、学到了什么?
1、有序列表的双指针排序方法