https://leetcode.com/problems/rle-iterator
Approach 1: Store Exhausted Position and Quantity
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 -1instead.
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".
We can store an index
i and quantity q which represents that q elements of A[i] (repeated A[i+1]times) are exhausted.
For example, if we have
A = [1,2,3,4] (mapping to the sequence [2,4,4,4]) then i = 0, q = 0represents that nothing is exhausted; i = 0, q = 1 represents that [2] is exhausted, i = 2, q = 1will represent that we have currently exhausted [2, 4], and so on.
Algorithm
Say we want to exhaust
n more elements. There are currently D = A[i] - q elements left to exhaust (of value A[i+1]).
If
n > D, then we should exhaust all of them and continue: n -= D; i += 2; q = 0.
Otherwise, we should exhaust some of them and return the current element's value:
q += D; return A[i+1].- Time Complexity: , where is the length of
A, and is the number of calls toRLEIterator.next. - Space Complexity: .
class RLEIterator {
int[] A;
int i, q;
public RLEIterator(int[] A) {
this.A = A;
i = q = 0;
}
public int next(int n) {
while (i < A.length) {
if (q + n > A[i]) {
n -= A[i] - q;
q = 0;
i += 2;
} else {
q += n;
return A[i + 1];
}
}
return -1;
}
}
https://leetcode.com/problems/rle-iterator/discuss/168286/Java-straightforward-code-with-comment-O(n)-time-and-O(1)-space
private int idx = 0;
private int[] A;
public RLEIterator(int[] A) { this.A = A; } // Injected A[]
public int next(int n) {
while (idx < A.length && n > A[idx]) { // exhaust as many terms as possible.
n -= A[idx]; // exhaust A[idx + 1] for A[idx] times.
idx += 2; // move to next term.
}
if (idx < A.length) { // not exhaust all terms.
A[idx] -= n;
return A[idx + 1];
}
return -1; // exhaust all terms but still not enough.
}class RLEIterator {
int index;
int [] A;
public RLEIterator(int[] A) {
this.A = A;
index = 0;
}
public int next(int n) {
while(index < A.length && n > A[index]){
n = n - A[index];
index += 2;
}
if(index >= A.length){
return -1;
}
A[index] = A[index] - n;
return A[index + 1];
}
}
