What is a run-length encoding?

Run-length encoding is a form of data compression where consecutive elements of the same value are stored as a single pair: [frequency, value].

How do I solve the Decompress Run-Length Encoded List problem?

You solve this problem by iterating through the array in pairs, expanding each pair [freq, val] by repeating 'val' 'freq' times, and appending it to the result list.

What are the time and space complexities for this problem?

The time complexity is O(n) where n is the length of the decompressed array. The space complexity is O(n) as well, due to the need to store the expanded list.

How can I optimize my solution for large inputs?

Use Python's list multiplication feature to efficiently repeat values, and minimize memory consumption by directly appending to the result list.

What should I watch out for when solving this problem?

Be careful with handling cases where the input list might contain non-even pairs or large frequency values that lead to expanded lists.

#1313

Easy

auto_awesome数组·driven

LeetCode 题解工作台

解压缩编码列表

给你一个以行程长度编码压缩的整数列表 nums 。考虑每对相邻的两个元素 [freq, val] = [nums[2*i], nums[2*i+1]] （其中 i >= 0 ），每一对都表示解压后子列表中有 freq 个值为 val 的元素，你需要从左到右连接所有子列表以生成解压后的列表。请你返…

数组

题目描述

给你一个以行程长度编码压缩的整数列表 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 <= 100
nums.length % 2 == 0
1 <= nums[i] <= 100

lightbulb

解题思路

方法一：模拟

我们可以直接模拟题目描述的过程，从左到右遍历数组 $\textit{nums}$ ，每次取出两个数 $\textit{freq}$ 和 $\textit{val}$ ，然后将 $\textit{val}$ 重复 $\textit{freq}$ 次，将这 $\textit{freq}$ 个 $\textit{val}$ 加入答案数组即可。

时间复杂度 $O(n)$ ，其中 $n$ 是数组 $\textit{nums}$ 的长度。我们只需要遍历一次数组 $\textit{nums}$ 即可。忽略答案数组的空间消耗，空间复杂度 $O(1)$ 。

1

2

3

4

class Solution:
    def decompressRLElist(self, nums: List[int]) -> List[int]:
        return [nums[i + 1] for i in range(0, len(nums), 2) for _ in range(nums[i])]

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Check if the candidate understands the run-length encoding and how to iterate through pairs.
question_mark
Observe if the candidate uses list operations efficiently to minimize overhead.
question_mark
Assess whether the candidate avoids excessive space usage by directly modifying the result.

warning

常见陷阱

外企场景

error
Incorrectly handling the case where nums contains an odd number of elements or non-even pairs.
error
Using inefficient techniques like repeated manual loops instead of list operations for value repetition.
error
Not ensuring that the result list is built in an optimal way, possibly leading to high memory consumption.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Given an input of varying length, test if the solution scales with different amounts of input data.
arrow_right_alt
Test the case with large frequency values to see if the solution can handle arrays with high expansion factors.
arrow_right_alt
Introduce more complex encoding schemes with additional data types or constraints to test adaptability.

help

常见问题

外企场景

继续练习

#1314 矩阵区域和 #1311 获取你好友已观看的视频 #1310 子数组异或查询