900. RLE Iterator
Description
We can use run-length encoding (i.e., RLE) to encode a sequence of integers. In a run-length encoded array of even length encoding
(0-indexed), for all even i
, encoding[i]
tells us the number of times that the non-negative integer value encoding[i + 1]
is repeated in the sequence.
- For example, the sequence
arr = [8,8,8,5,5]
can be encoded to beencoding = [3,8,2,5]
.encoding = [3,8,0,9,2,5]
andencoding = [2,8,1,8,2,5]
are also valid RLE ofarr
.
Given a run-length encoded array, design an iterator that iterates through it.
Implement the RLEIterator
class:
RLEIterator(int[] encoded)
Initializes the object with the encoded arrayencoded
.int next(int n)
Exhausts the nextn
elements and returns the last element exhausted in this way. If there is no element left to exhaust, return-1
instead.
Example 1:
Input ["RLEIterator", "next", "next", "next", "next"] [[[3, 8, 0, 9, 2, 5]], [2], [1], [1], [2]] Output [null, 8, 8, 5, -1] Explanation RLEIterator rLEIterator = new RLEIterator([3, 8, 0, 9, 2, 5]); // This maps to the sequence [8,8,8,5,5]. rLEIterator.next(2); // exhausts 2 terms of the sequence, returning 8. The remaining sequence is now [8, 5, 5]. rLEIterator.next(1); // exhausts 1 term of the sequence, returning 8. The remaining sequence is now [5, 5]. rLEIterator.next(1); // exhausts 1 term of the sequence, returning 5. The remaining sequence is now [5]. rLEIterator.next(2); // exhausts 2 terms, returning -1. This is because the first term exhausted was 5, but the second term did not exist. Since the last term exhausted does not exist, we return -1.
Constraints:
2 <= encoding.length <= 1000
encoding.length
is even.0 <= encoding[i] <= 109
1 <= n <= 109
- At most
1000
calls will be made tonext
.
Solutions
Solution 1: Maintain Two Pointers
We define two pointers $i$ and $j$, where pointer $i$ points to the current run-length encoding being read, and pointer $j$ points to which character in the current run-length encoding is being read. Initially, $i = 0$, $j = 0$.
Each time we call next(n)
, we judge whether the remaining number of characters in the current run-length encoding $encoding[i] - j$ is less than $n$. If it is, we subtract $n$ by $encoding[i] - j$, add $2$ to $i$, and set $j$ to $0$, then continue to judge the next run-length encoding. If it is not, we add $n$ to $j$ and return $encoding[i + 1]$.
If $i$ exceeds the length of the run-length encoding and there is still no return value, it means that there are no remaining elements to be exhausted, and we return $-1$.
The time complexity is $O(n + q)$, and the space complexity is $O(n)$. Here, $n$ is the length of the run-length encoding, and $q$ is the number of times next(n)
is called.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
|