将元素分配到两个数组中 I

难度: Easy

给你一个下标从 1 开始、包含不同整数的数组 nums ，数组长度为 n 。

你需要通过 n 次操作，将 nums 中的所有元素分配到两个数组 arr1 和 arr2 中。在第一次操作中，将 nums[1] 追加到 arr1 。在第二次操作中，将 nums[2] 追加到 arr2 。之后，在第 i 次操作中：

如果 arr1 的最后一个元素大于 arr2 的最后一个元素，就将 nums[i] 追加到 arr1 。否则，将 nums[i] 追加到 arr2 。

通过连接数组 arr1 和 arr2 形成数组 result 。例如，如果 arr1 == [1,2,3] 且 arr2 == [4,5,6] ，那么 result = [1,2,3,4,5,6] 。

返回数组 result 。

示例 1：

输入：nums = [2,1,3]
输出：[2,3,1]
解释：在前两次操作后，arr1 = [2] ，arr2 = [1] 。
在第 3 次操作中，由于 arr1 的最后一个元素大于 arr2 的最后一个元素（2 > 1），将 nums[3] 追加到 arr1 。
3 次操作后，arr1 = [2,3] ，arr2 = [1] 。
因此，连接形成的数组 result 是 [2,3,1] 。

示例 2：

输入：nums = [5,4,3,8]
输出：[5,3,4,8]
解释：在前两次操作后，arr1 = [5] ，arr2 = [4] 。
在第 3 次操作中，由于 arr1 的最后一个元素大于 arr2 的最后一个元素（5 > 4），将 nums[3] 追加到 arr1 ，因此 arr1 变为 [5,3] 。
在第 4 次操作中，由于 arr2 的最后一个元素大于 arr1 的最后一个元素（4 > 3），将 nums[4] 追加到 arr2 ，因此 arr2 变为 [4,8] 。
4 次操作后，arr1 = [5,3] ，arr2 = [4,8] 。
因此，连接形成的数组 result 是 [5,3,4,8] 。

提示：

3 <= n <= 50
1 <= nums[i] <= 100
nums中的所有元素都互不相同。

Submission

运行时间: 16 ms

内存: 16.0 MB

class Solution:
    def resultArray(self, nums: List[int]) -> List[int]:
        res = []
        n = len(nums)
        if n == 1:
            return nums
        arr1 = [nums[0]]
        arr2 = [nums[1]]
        
        i = 2
        while i < n:
            if arr1[-1] > arr2[-1]:
                arr1.append(nums[i])
            else:
                arr2.append(nums[i])
            i += 1
        arr1.extend(arr2)
        return arr1

Explain

题解首先初始化两个数组arr1和arr2，将nums数组的前两个元素分别放入这两个数组。然后，从第三个元素开始，依次判断arr1的最后一个元素和arr2的最后一个元素的大小。如果arr1的最后一个元素大于arr2的最后一个元素，则将当前元素添加到arr1中；否则，添加到arr2中。遍历完成后，将arr2的所有元素追加到arr1后面，返回arr1作为结果。这种方法直接根据题目要求进行元素的分配，然后合并两个数组形成最终结果。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def resultArray(self, nums: List[int]) -> List[int]:
        res = []  # 初始化结果数组，但在代码中未使用
        n = len(nums)  # 获取输入数组的长度
        if n == 1:
            return nums  # 如果数组只有一个元素，直接返回
        arr1 = [nums[0]]  # 初始化arr1，将第一个元素加入arr1
        arr2 = [nums[1]]  # 初始化arr2，将第二个元素加入arr2
        
        i = 2  # 从第三个元素开始处理
        while i < n:  # 遍历nums中的剩余元素
            if arr1[-1] > arr2[-1]:  # 比较arr1和arr2最后一个元素的大小
                arr1.append(nums[i])  # 如果arr1的最后一个元素大，则追加到arr1
            else:
                arr2.append(nums[i])  # 否则追加到arr2
            i += 1  # 移动到下一个元素
        arr1.extend(arr2)  # 将arr2的元素追加到arr1后面
        return arr1  # 返回结果

Explore

题解的方法在处理只有两个元素的数组时直接将第一个元素放入arr1，第二个元素放入arr2，这种做法简单且符合题目的基本要求，即将数组分配到两个子数组中。在这种情况下，由于题目没有提供特别的排序或其他条件，这种分配方式是合理的，能够满足题目的基本操作规则。

题解中提到的处理单一元素数组的方法是直接返回该数组。这种处理方式符合题目的基本操作规则，因为题目要求是将元素分配到两个数组中，如果只有一个元素，那么可以认为它已经被分配到一个数组中（arr1），而arr2为空。因此，直接返回该元素作为arr1的结果是合理的。

题解中将arr2的所有元素追加到arr1后，确实应该验证arr1的元素总数是否等于nums的长度，以确保没有元素被遗漏。这是一个重要的验证步骤，可以通过比较arr1的长度和nums的长度来进行。如果长度相等，则说明所有元素都被正确处理和包含在最终结果中；如果不等，则表明在分配或合并的过程中可能有遗漏或错误。