Problem
Write an iterator that iterates through a run-length encoded sequence.
The iterator is initialized by RLEIterator(int[] A), where A is a run-length encoding of some sequence. More specifically, for all even i, A[i] tells us the number of times that the non-negative integer value A[i+1] is repeated in the sequence.
The iterator supports one function: next(int n), which exhausts the next n elements (n >= 1) and returns the last element exhausted in this way. If there is no element left to exhaust, next returns -1 instead.
For example, we start with A = [3,8,0,9,2,5], which is a run-length encoding of the sequence [8,8,8,5,5]. This is because the sequence can be read as “three eights, zero nines, two fives”.
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 is initialized with RLEIterator([3,8,0,9,2,5]).
This maps to the sequence [8,8,8,5,5].
RLEIterator.next is then called 4 times:
.next(2) exhausts 2 terms of the sequence, returning 8. The remaining sequence is now [8, 5, 5].
.next(1) exhausts 1 term of the sequence, returning 8. The remaining sequence is now [5, 5].
.next(1) exhausts 1 term of the sequence, returning 5. The remaining sequence is now [5].
.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.
Note:
0 <= A.length <= 1000A.length is an even integer.0 <= A[i] <= 10^9- There are at most
1000 calls to RLEIterator.next(int n) per test case.
- Each call to
RLEIterator.next(int n) will have 1 <= n <= 10^9.
Solution: Simulation
Time complexity: O(|A|)
Space complexity: O(|A|)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
// Author: Huahua, 4 ms class RLEIterator { public: RLEIterator(vector<int> A): A_(std::move(A)), i_(0) {} int next(int n) { while (n && i_ < A_.size()) { if (n >= A_[i_]) { n -= A_[i_]; i_ += 2; if (n == 0) return A_[i_ - 1]; } else { A_[i_] -= n; return A_[i_ + 1]; } } return -1; } private: int i_; vector<int> A_; }; |
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
// Author: Huahua, 73 ms class RLEIterator { private int[] A; private int i; public RLEIterator(int[] A) { this.A = A; this.i = 0; } public int next(int n) { while (n >= 0 && i < A.length) { if (n >= A[i]) { n -= A[i]; i += 2; if (n == 0) return A[i - 1]; } else { A[i] -= n; return A[i + 1]; } } return -1; } } |
Python3
|
|
# Author: Huahua, 44 ms class RLEIterator: def __init__(self, A): self.A = A self.i = 0 def next(self, n): while n != 0 and self.i < len(self.A): if n >= self.A[self.i]: n -= self.A[self.i] self.i += 2 if n == 0: return self.A[self.i - 1] else: self.A[self.i] -= n return self.A[self.i + 1] return -1 |