两个行程编码数组的积
难度:
标签:
题目描述
代码结果
运行时间: 211 ms, 内存: 67.1 MB
/*
* LeetCode 1868: Product of Two Run-Length Encoded Arrays
*
* Approach using Java Streams:
* We will use streams to process the two arrays in a functional style.
* The core idea is similar: use streams to iterate over the elements,
* compute the product for corresponding elements, and combine frequencies.
*/
import java.util.ArrayList;
import java.util.List;
import java.util.stream.IntStream;
public class SolutionStream {
public List<int[]> findRLEArray(int[][] encoded1, int[][] encoded2) {
List<int[]> result = new ArrayList<>();
int[] i = {0};
int[] j = {0};
while (i[0] < encoded1.length && j[0] < encoded2.length) {
int value1 = encoded1[i[0]][0];
int freq1 = encoded1[i[0]][1];
int value2 = encoded2[j[0]][0];
int freq2 = encoded2[j[0]][1];
int minFreq = Math.min(freq1, freq2);
int product = value1 * value2;
if (!result.isEmpty() && result.get(result.size() - 1)[0] == product) {
result.get(result.size() - 1)[1] += minFreq;
} else {
result.add(new int[]{product, minFreq});
}
encoded1[i[0]][1] -= minFreq;
encoded2[j[0]][1] -= minFreq;
if (encoded1[i[0]][1] == 0) i[0]++;
if (encoded2[j[0]][1] == 0) j[0]++;
}
return result;
}
}
解释
方法:
此题解的核心思路是将两个行程编码数组(每个数组中的元素由[value, count]组成,表示value出现count次)进行逐对元素的乘积,并且保持行程编码的形式。算法逐一比较两个数组中的当前元素,计算乘积,并更新计数。如果两数组当前元素的计数不一致,则减少计数较小的数组的当前元素的计数,并将其指针前移,否则同时前移两数组的指针。当两数组相应计数的乘积与之前的乘积相同,合并计数;否则,将当前乘积和计数作为新的元素添加到结果数组中。
时间复杂度:
O(m+n)
空间复杂度:
O(m+n)
代码细节讲解
🦆
算法在处理两个数组的计数不一致时,仅减少计数较小的数组的当前计数,并前移指针,这种处理对结果的正确性有何影响?
▷🦆
当两个数组的元素乘积相同时,算法选择累加计数而非立即产生新的结果元素,这种做法的优势在哪里?
▷🦆
在算法的最后,直接将当前乘积和计数添加到结果数组中,这里是否考虑到了所有可能的边界情况?
▷🦆
在处理两个数组的元素时,如果遇到一个数组先遍历完毕的情况,题解中没有明确说明如何处理剩下的元素。这种情况下应如何处理?
▷