Easy

题目描述

给你一个下标从 1 开始、长度为 n 的整数数组 nums，数组中的元素互不相同。

你需要通过 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 中的所有元素互不相同

解题思路

这是一道直观的模拟题，需要严格按照题目描述的规则进行操作。

解题思路：

  1. 初始化两个数组：创建 arr1 和 arr2 两个空数组
  2. 前两次操作：将 nums[0] 添加到 arr1，将 nums[1] 添加到 arr2
  3. 后续操作：从第三个元素开始（索引 2），比较两个数组的最后一个元素
    • 如果 arr1 的最后元素大于 arr2 的最后元素，将当前元素添加到 arr1
    • 否则添加到 arr2
  4. 合并结果：将 arr1 和 arr2 连接起来形成最终结果

关键点：

  • 题目描述中使用 1-indexed，但实际编程时需要转换为 0-indexed
  • 需要动态跟踪两个数组的最后元素进行比较
  • 最后需要按顺序连接两个数组

时间复杂度为 O(n)，空间复杂度为 O(n)，其中 n 是输入数组的长度。

代码实现

class Solution {
public:
    vector<int> resultArray(vector<int>& nums) {
        vector<int> arr1, arr2;
        
        // 前两次操作
        arr1.push_back(nums[0]);
        arr2.push_back(nums[1]);
        
        // 后续操作
        for (int i = 2; i < nums.size(); i++) {
            if (arr1.back() > arr2.back()) {
                arr1.push_back(nums[i]);
            } else {
                arr2.push_back(nums[i]);
            }
        }
        
        // 合并结果
        vector<int> result = arr1;
        result.insert(result.end(), arr2.begin(), arr2.end());
        
        return result;
    }
};

class Solution:
    def resultArray(self, nums: List[int]) -> List[int]:
        arr1, arr2 = [], []
        
        # 前两次操作
        arr1.append(nums[0])
        arr2.append(nums[1])
        
        # 后续操作
        for i in range(2, len(nums)):
            if arr1[-1] > arr2[-1]:
                arr1.append(nums[i])
            else:
                arr2.append(nums[i])
        
        # 合并结果
        return arr1 + arr2

public class Solution {
    public int[] ResultArray(int[] nums) {
        List<int> arr1 = new List<int>();
        List<int> arr2 = new List<int>();
        
        // 前两次操作
        arr1.Add(nums[0]);
        arr2.Add(nums[1]);
        
        // 后续操作
        for (int i = 2; i < nums.Length; i++) {
            if (arr1[arr1.Count - 1] > arr2[arr2.Count - 1]) {
                arr1.Add(nums[i]);
            } else {
                arr2.Add(nums[i]);
            }
        }
        
        // 合并结果
        List<int> result = new List<int>(arr1);
        result.AddRange(arr2);
        
        return result.ToArray();
    }
}

var resultArray = function(nums) {
    let arr1 = [], arr2 = [];
    
    // 前两次操作
    arr1.push(nums[0]);
    arr2.push(nums[1]);
    
    // 后续操作
    for (let i = 2; i < nums.length; i++) {
        if (arr1[arr1.length - 1] > arr2[arr2.length - 1]) {
            arr1.push(nums[i]);
        } else {
            arr2.push(nums[i]);
        }
    }
    
    // 合并结果
    return arr1.concat(arr2);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历数组一次，每次操作为常数时间
空间复杂度O(n)需要额外空间存储两个数组和结果数组

相关题目