leetcode
leetcode 1651 ~ 1700
两个行程编码数组的积

两个行程编码数组的积

难度:

标签:

题目描述

代码结果

运行时间: 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)

代码细节讲解

🦆
算法在处理两个数组的计数不一致时,仅减少计数较小的数组的当前计数,并前移指针,这种处理对结果的正确性有何影响?
这种处理方式确保了算法的正确性,因为它允许两个数组中对应的元素按照实际出现的次数进行乘积运算。当一个数组的当前元素的计数小于另一个数组时,通过减少等量的计数并前移指针,可以确保每个元素都被完全且正确地处理,而不会有遗漏或重复。此操作保证了两个数组的元素在运算中的对应性,使得最终的行程编码数组能准确反映出所有可能的乘积及其出现次数。
🦆
当两个数组的元素乘积相同时,算法选择累加计数而非立即产生新的结果元素,这种做法的优势在哪里?
选择累加计数而非立即产生新的结果元素可以有效减少结果数组的大小,从而优化存储空间的使用。在行程编码中,相同值的连续出现可以合并为一个元素,减少了数组的元素数量,提高了空间效率。此外,这种做法还减少了数组操作的次数,可能对算法的运行时间也有一定的优化效果。
🦆
在算法的最后,直接将当前乘积和计数添加到结果数组中,这里是否考虑到了所有可能的边界情况?
算法的这一处理确实考虑到了所有边界情况。由于在每次循环中,只有在当前乘积发生变化时才会将之前的乘积与计数存入结果数组,而最后一组乘积和计数在循环结束时可能尚未被添加。因此,在循环结束后直接添加最后一组乘积和计数确保了包括最后一次计算在内的所有乘积都被正确记录。
🦆
在处理两个数组的元素时,如果遇到一个数组先遍历完毕的情况,题解中没有明确说明如何处理剩下的元素。这种情况下应如何处理?
在题目的上下文中,一旦一个数组遍历完成,另一个数组中剩下的元素实际上不需要再处理,因为行程编码表示的是有限的元素和其出现次数。如果其中一个数组已经处理完毕,意味着没有更多的元素来与另一个数组中的剩余元素相乘。因此,这种情况下,算法不需要对剩余的元素进行额外的处理,直接结束即可。

相关问题