标签: 数组
难度: 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] 代表着 2 的出现频次为 1，所以生成数组 [2]。 第二对 [3,4] 代表着 4 的出现频次为 3，所以生成数组 [4,4,4]。 最后将它们串联到一起 [2] + [4,4,4] = [2,4,4,4]。
示例 2：
输入：nums = [1,1,2,3] 输出：[1,3,3]
提示：
2 <= nums.length <= 100nums.length % 2 == 01 <= nums[i] <= 100运行时间: 20 ms
内存: 16.1 MB
class Solution:
def decompressRLElist(self, nums: List[int]) -> List[int]:
res = list()
for i in range(0, len(nums), 2):
res.extend([nums[i + 1]] * nums[i])
return res
这道题的思路是通过遍历输入列表，每次取出一对 `[freq, val]`，然后根据 `freq` 的值生成由 `val` 组成的列表，并将这些列表拼接起来。遍历时步长为2，因为每次处理一对元素。
时间复杂度: O(n^2)
空间复杂度: O(n)
class Solution:
def decompressRLElist(self, nums: List[int]) -> List[int]:
res = [] # 初始化结果列表
for i in range(0, len(nums), 2): # 遍历输入列表，步长为2
res.extend([nums[i + 1]] * nums[i]) # 将 val 复制 freq 次，并添加到结果列表中
return res # 返回解压后的列表
是的，算法在处理每对 `[freq, val]` 时已经默默地考虑了 `freq` 为 0 的情况。因为当 `freq` 为 0 时，`[nums[i + 1]] * nums[i]` 这一表达式会产生一个空列表，随后使用 `extend` 方法添加到 `res` 列表中时不会有任何变化。因此，如果 `freq` 为 0，结果列表不会添加任何元素，这符合题目的要求。
是的，`extend` 方法的内部实现会影响算法的整体性能。`extend` 方法添加一个列表到另一个列表的时间复杂度取决于被添加列表的长度。在本题中，`extend` 被用来添加由 `val` 重复 `freq` 次形成的列表。如果 `freq` 很大，那么重复操作和内存分配可能会较为耗时。然而，使用 `extend` 方法通常比逐个添加元素更高效，因为它可以优化内存分配和减少中间操作。
虽然当前的方法已经相对高效，但理论上可以考虑其他方法来优化内存使用和执行速度。例如，可以使用 NumPy 库直接在内存中构建和扩展数组，该库底层使用 C 语言实现，可以提供更快的数组操作性能。此外，如果在一个高级语言环境中实现，可以考虑使用生成器（generator）来延迟生成并逐个处理元素，这样可以减少一次性内存分配的需求。然而，这些方法可能需要额外的库支持和更复杂的实现。在大多数实际应用中，直接使用列表和 `extend` 方法已经足够高效和简单。