Easy

题目描述

给你一个以行程长度编码压缩的整数列表 nums。

考虑每对相邻的元素 [freq, val] = [nums[2*i], nums[2*i+1]]（其中 i >= 0）。对于每一对，都有 freq 个值为 val 的元素在子列表中。将所有子列表从左到右连接以生成解压缩后的列表。

返回解压缩后的列表。

示例 1：

输入：nums = [1,2,3,4]
输出：[2,4,4,4]
解释：第一对 [1,2] 代表着 freq = 1 且 val = 2，所以它生成数组 [2]。
第二对 [3,4] 代表着 freq = 3 且 val = 4，所以它生成数组 [4,4,4]。
最后将它们进行连接 [2] + [4,4,4] = [2,4,4,4]。

示例 2：

输入：nums = [1,1,2,3]
输出：[1,3,3]

提示：

  • 2 <= nums.length <= 100
  • nums.length % 2 == 0
  • 1 <= nums[i] <= 100

解题思路

解题思路

这是一道简单的模拟题，主要考查对游程编码（Run-Length Encoding）的理解和数组操作。

核心思想： 游程编码将连续重复的数据压缩成"频次-数值"对的形式。题目给出的数组按照 [freq1, val1, freq2, val2, ...] 的格式排列，我们需要将其还原为原始数组。

算法步骤：

  1. 遍历输入数组，每次取两个元素作为一对
  2. 对于每对 [freq, val]，将值 val 重复 freq 次
  3. 将所有重复的结果依次添加到结果数组中

实现方法：

  • 方法一（推荐）： 直接遍历，使用内层循环添加重复元素
  • 方法二： 先计算结果数组大小，预分配空间后填充（适合对性能要求较高的场景）

时间复杂度主要取决于输出数组的大小，空间复杂度为输出数组的空间。整体实现思路简单直观，是典型的模拟题解法。

代码实现

class Solution {
public:
    vector<int> decompressRLElist(vector<int>& nums) {
        vector<int> result;
        for (int i = 0; i < nums.size(); i += 2) {
            int freq = nums[i];
            int val = nums[i + 1];
            for (int j = 0; j < freq; j++) {
                result.push_back(val);
            }
        }
        return result;
    }
};

class Solution:
    def decompressRLElist(self, nums: List[int]) -> List[int]:
        result = []
        for i in range(0, len(nums), 2):
            freq = nums[i]
            val = nums[i + 1]
            result.extend([val] * freq)
        return result

public class Solution {
    public int[] DecompressRLElist(int[] nums) {
        List<int> result = new List<int>();
        for (int i = 0; i < nums.Length; i += 2) {
            int freq = nums[i];
            int val = nums[i + 1];
            for (int j = 0; j < freq; j++) {
                result.Add(val);
            }
        }
        return result.ToArray();
    }
}

var decompressRLElist = function(nums) {
    let result = [];
    for (let i = 0; i < nums.length; i += 2) {
        let freq = nums[i];
        let val = nums[i + 1];
        for (let j = 0; j < freq; j++) {
            result.push(val);
        }
    }
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)n 为解压后数组的长度，需要遍历所有输出元素
空间复杂度O(1)除了输出数组外，只使用常数级额外空间

相关题目