88. Merge Sorted Array

Two pointer/Sorted array

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Merge nums1 and nums2 into a single array sorted in non-decreasing order.

The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

\

My solution

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.
        """
        if (m != 0 and n != 0):
            x_idx, y_idx = 0, 0
            while (x_idx < m+y_idx and y_idx < n):
                if (nums1[x_idx] <= nums2[y_idx]):
                    x_idx += 1
                else:
                    nums1[x_idx+1:m+y_idx+1] = nums1[x_idx:m+y_idx]
                    nums1[x_idx] = nums2[y_idx]
                    x_idx += 1
                    y_idx += 1
            if (x_idx == m+y_idx):
                nums1[x_idx:len(nums1)] = nums2[y_idx:n]
        elif (m == 0):
            nums1[:] = nums2
        else:
            nums1 = nums1

problems:

• At first I use nums1[x_idx:m+y_idx+1] = nums1[x_idx:m+y_idx] , which cause overlapping, I change that to nums1[x_idx+2:m+y_idx+1] = nums1[x_idx:m+y_idx]
• nums1 = nums2不会改变原数组，改为nums1[:n] = nums2
• 每次插入都移动大量数据，后面有很长一段空数组，应该改为从后向前插入

\

Solution

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.
    """
		    p1, p2, p = m-1, n-1, n+m-1
		    while p1 > 0 and p2 > 0:
				    if nums1[p1] > nums2[p2]:
						    nums1[p] = nums1[p1]
						    p1 -= 1
						else:
								nums1[p] = nums2[p2]
								pw -= 1
						p -= 1 #这一项两个条件都要用到，可以直接移出来
				nums1[:p2+1] = nums2[:p2+1]
				# 结束while循环，有以下两种情况，
				# 1. nums1的已经加完了，p1 <= 0，剩下的全部加nums2的
				# 2. nums2的已经加完了，[:p2+1]为[:0]
				# Edge Case，nums1/nums2为空，已经包含在上述两种情况中，相当于主循环结束，其中一个array已经被加完了

27. Remove Elements

Two pointer/Sorted array

Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The order of the elements may be changed. Then return the number of elements in nums which are not equal to val.

Consider the number of elements in nums which are not equal to val be k, to get accepted, you need to do the following things:

• Change the array nums such that the first k elements of nums contain the elements which are not equal to val. The remaining elements of nums are not important as well as the size of nums.