Description
We are given a list nums of integers representing a list compressed with run-length encoding.
Consider each adjacent pair of elements [freq, val] = [nums[2*i], nums[2*i+1]] (with i >= 0). For each such pair, there are freq elements with value val concatenated in a sublist. Concatenate all the sublists from left to right to generate the decompressed list.
Return the decompressed list.
Example 1:
Input: nums = [1,2,3,4]
Output: [2,4,4,4]
Explanation: The first pair [1,2] means we have freq = 1 and val = 2 so we generate the array [2].
The second pair [3,4] means we have freq = 3 and val = 4 so we generate [4,4,4].
At the end the concatenation [2] + [4,4,4] is [2,4,4,4].
Example 2:
Input: nums = [1,1,2,3]
Output: [1,3,3]
Constraints:
2 <= nums.length <= 100nums.length % 2 == 01 <= nums[i] <= 100
Solutions
Solution 1: Simulation
We can directly simulate the process described in the problem. Traverse the array nums from left to right, each time taking out two numbers freq and val, then repeat val freq times, and add these freq vals to the answer array.
The time complexity is O(n), where n is the length of the array nums. We only need to traverse the array nums once. Ignoring the space consumption of the answer array, the space complexity is O(1).
PythonJavaC++GoTypeScriptRustC
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])](code-box)
class Solution {
public int[] decompressRLElist(int[] nums) {
List<Integer> ans = new ArrayList<>();
for (int i = 0; i < nums.length; i += 2) {
for (int j = 0; j < nums[i]; ++j) {
ans.add(nums[i + 1]);
}
}
return ans.stream().mapToInt(i -> i).toArray();
}
}(code-box)
class Solution {
public:
vector<int> decompressRLElist(vector<int>& nums) {
vector<int> ans;
for (int i = 0; i < nums.size(); i += 2) {
for (int j = 0; j < nums[i]; j++) {
ans.push_back(nums[i + 1]);
}
}
return ans;
}
};(code-box)
func decompressRLElist(nums []int) (ans []int) {
for i := 1; i < len(nums); i += 2 {
for j := 0; j < nums[i-1]; j++ {
ans = append(ans, nums[i])
}
}
return
}(code-box)
function decompressRLElist(nums: number[]): number[] {
const ans: number[] = [];
for (let i = 0; i < nums.length; i += 2) {
for (let j = 0; j < nums[i]; j++) {
ans.push(nums[i + 1]);
}
}
return ans;
}(code-box)
impl Solution {
pub fn decompress_rl_elist(nums: Vec<i32>) -> Vec<i32> {
let mut ans = Vec::new();
let n = nums.len();
let mut i = 0;
while i < n {
let freq = nums[i];
let val = nums[i + 1];
for _ in 0..freq {
ans.push(val);
}
i += 2;
}
ans
}
}(code-box)
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* decompressRLElist(int* nums, int numsSize, int* returnSize) {
int n = 0;
for (int i = 0; i < numsSize; i += 2) {
n += nums[i];
}
int* ans = (int*) malloc(n * sizeof(int));
*returnSize = n;
int k = 0;
for (int i = 0; i < numsSize; i += 2) {
int freq = nums[i];
int val = nums[i + 1];
for (int j = 0; j < freq; j++) {
ans[k++] = val;
}
}
return ans;
}(code-box)
