88. Merge Sorted Array

题目要求：

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
把nums2有序的插入到nums1里面。

Note:
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectively.

解题思路：

• 这道题目又是利用现有空间不开辟新空间进行排序的题目。
• 将nums1和nums2从后面开始比较（本来两个数组的就是升序），大的进行冒泡。
• 示意图

# Time:  O(n)
# Space: O(1)
#
# Given two sorted integer arrays A and B, merge B into A as one sorted array.
# 
# Note:
# You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements from B. 
# The number of elements initialized in A and B are m and n respectively.
#

class Solution(object):
    def sortColors(self, nums):
        """
        :param nums: List[int]
        :return: void Do not return anything, modify nums in-place instead.
        """
        def triPartition(nums, target):
            i, j, n = 0, 0, len(nums) - 1

            while j <= n:
                if nums[j] > target:
                    nums[j], nums[n] = nums[n], nums[j]
                    n -= 1

                elif nums[j] < target:
                    nums[i], nums[j] = nums[j], nums[i]
                    j += 1
                    i += 1
                else:
                    j += 1

        triPartition(nums, 1)


if __name__ == "__main__":
    A = [2, 1, 1, 0, 0, 2]
    Solution().sortColors(A)
    print(A)