一刷 07/2022
Versino #2 Merge Intervals
Time O(Length of encoded1 + Length of encoded2)
Space O(1)Runtime: 25 ms, faster than 93.63% of Java online submissions for Product of Two Run-Length Encoded Arrays.
class Solution {
public List<List<Integer>> findRLEArray(int[][] encoded1, int[][] encoded2) {
int p1 = 0, p2 = 0;
List<List<Integer>> result = new ArrayList<>();
int prevProduct = 0;
int prevCount = 0;
while (p1 < encoded1.length && p2 < encoded2.length) {
int product = encoded1[p1][0] * encoded2[p2][0];
int count = 0;
if (encoded1[p1][1] == encoded2[p2][1]) {
count = encoded1[p1][1];
p1++;
p2++;
} else if (encoded1[p1][1] < encoded2[p2][1]) {
count = encoded1[p1][1];
encoded2[p2][1] -= encoded1[p1][1];
p1++;
} else {
count = encoded2[p2][1];
encoded1[p1][1] -= encoded2[p2][1];
p2++;
}
if (product == prevProduct) {
prevCount += count;
} else {
if (prevCount != 0) {
result.add(Arrays.asList(new Integer[]{prevProduct, prevCount}));
}
prevProduct = product;
prevCount = count;
}
}
if (prevCount != 0) {
result.add(Arrays.asList(new Integer[]{prevProduct, prevCount}));
}
return result;
}
}
Version #1 Increment step by one - TLE
Time O(Sum of encoded1 segment lengths + Sum of encoded2 segment lengths)
Space O(1)
class Solution {
public List<List<Integer>> findRLEArray(int[][] encoded1, int[][] encoded2) {
// encoded1 and encoded2 have the same length
int p1 = 0, p2 = 0;
List<List<Integer>> result = new ArrayList<>();
int curr = -1;
int count = 0;
while (p1 < encoded1.length && p2 < encoded2.length) {
if (encoded1[p1][1] == 0) {
p1++;
continue;
}
if (encoded2[p2][1] == 0) {
p2++;
continue;
}
int product = encoded1[p1][0] * encoded2[p2][0];
if (product == curr) {
count++;
} else {
if (count > 0) {
result.add(Arrays.asList(new Integer[]{curr, count}));
}
curr = product;
count = 1;
}
encoded1[p1][1]--;
encoded2[p2][1]--;
}
if (count > 0) {
result.add(Arrays.asList(new Integer[]{curr, count}));
}
return result;
}
}
No comments:
Post a Comment