一、前记(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、有序列表的双指针排序方法