跳转至

1868. 两个行程编码数组的积 🔒

题目描述

行程编码（Run-length encoding）是一种压缩算法，能让一个含有许多段连续重复数字的整数类型数组 nums 以一个（通常更小的）二维数组 encoded 表示。每个 encoded[i] = [vali, freqi] 表示 nums 中第 i 段重复数字，其中 vali 是该段重复数字，重复了 freqi 次。

  • 例如， nums = [1,1,1,2,2,2,2,2] 可表示称行程编码数组 encoded = [[1,3],[2,5]] 。对此数组的另一种读法是“三个 1 ，后面有五个 2 ”。

两个行程编码数组 encoded1 和 encoded2 的积可以按下列步骤计算：

  1. 将 encoded1 和 encoded2 分别扩展成完整数组 nums1 和 nums2 。
  2. 创建一个新的数组 prodNums ，长度为 nums1.length 并设 prodNums[i] = nums1[i] * nums2[i] 。
  3. 将 prodNums 压缩成一个行程编码数组并返回之。

给定两个行程编码数组 encoded1 和 encoded2 ，分别表示完整数组 nums1 和 nums2 。nums1 和 nums2 的长度相同。 每一个 encoded1[i] = [vali, freqi] 表示 nums1 中的第 i 段，每一个 encoded2[j] = [valj, freqj] 表示 nums2 中的第 j 段。

返回 encoded1 和 encoded2 的乘积。

注：行程编码数组需压缩成可能的最小长度。

 

示例 1:

输入: encoded1 = [[1,3],[2,3]], encoded2 = [[6,3],[3,3]]
输出: [[6,6]]
解释n: encoded1 扩展为 [1,1,1,2,2,2] ，encoded2 扩展为 [6,6,6,3,3,3]。
prodNums = [6,6,6,6,6,6]，压缩成行程编码数组 [[6,6]]。

示例 2:

输入: encoded1 = [[1,3],[2,1],[3,2]], encoded2 = [[2,3],[3,3]]
输出: [[2,3],[6,1],[9,2]]
解释: encoded1 扩展为 [1,1,1,2,3,3] ，encoded2 扩展为 [2,2,2,3,3,3]。
prodNums = [2,2,2,6,9,9]，压缩成行程编码数组 [[2,3],[6,1],[9,2]]。

 

提示：

  • 1 <= encoded1.length, encoded2.length <= 105
  • encoded1[i].length == 2
  • encoded2[j].length == 2
  • 对于每一个 encoded1[i]， 1 <= vali, freqi <= 104  
  • 对于每一个 encoded2[j]， 1 <= valj, freqj <= 104
  • encoded1 和 encoded2 表示的完整数组长度相同。

解法

方法一：双指针

我们用两个指针 $i$ 和 $j$ 分别指向两个数组的当前位置，然后开始模拟乘法的过程。

对于当前位置 $i$ 和 $j$，我们取 $f=min(encoded1[i][1],encoded2[j][1])$，表示当前位置的乘积的频次，然后将 $v=encoded1[i][0] \times encoded2[j][0]$，表示当前位置的乘积的值。如果当前位置的乘积的值 $v$ 和上一个位置的乘积的值相同，则将当前位置的乘积的频次加到上一个位置的乘积的频次上，否则将当前位置的乘积的值和频次加到答案数组中。然后我们将 $encoded1[i][1]$ 和 $encoded2[j][1]$ 分别减去 $f$，如果 $encoded1[i][1]$ 或 $encoded2[j][1]$ 减为 $0$，则将对应的指针向后移动一位。

最后返回答案数组即可。

时间复杂度 $O(m + n)$，其中 $m$ 和 $n$ 分别是两个数组的长度。忽略答案数组的空间消耗，空间复杂度 $O(1)$。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def findRLEArray(
        self, encoded1: List[List[int]], encoded2: List[List[int]]
    ) -> List[List[int]]:
        ans = []
        j = 0
        for vi, fi in encoded1:
            while fi:
                f = min(fi, encoded2[j][1])
                v = vi * encoded2[j][0]
                if ans and ans[-1][0] == v:
                    ans[-1][1] += f
                else:
                    ans.append([v, f])
                fi -= f
                encoded2[j][1] -= f
                if encoded2[j][1] == 0:
                    j += 1
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public List<List<Integer>> findRLEArray(int[][] encoded1, int[][] encoded2) {
        List<List<Integer>> ans = new ArrayList<>();
        int j = 0;
        for (var e : encoded1) {
            int vi = e[0], fi = e[1];
            while (fi > 0) {
                int f = Math.min(fi, encoded2[j][1]);
                int v = vi * encoded2[j][0];
                int m = ans.size();
                if (m > 0 && ans.get(m - 1).get(0) == v) {
                    ans.get(m - 1).set(1, ans.get(m - 1).get(1) + f);
                } else {
                    ans.add(new ArrayList<>(List.of(v, f)));
                }
                fi -= f;
                encoded2[j][1] -= f;
                if (encoded2[j][1] == 0) {
                    ++j;
                }
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    vector<vector<int>> findRLEArray(vector<vector<int>>& encoded1, vector<vector<int>>& encoded2) {
        vector<vector<int>> ans;
        int j = 0;
        for (auto& e : encoded1) {
            int vi = e[0], fi = e[1];
            while (fi) {
                int f = min(fi, encoded2[j][1]);
                int v = vi * encoded2[j][0];
                if (!ans.empty() && ans.back()[0] == v) {
                    ans.back()[1] += f;
                } else {
                    ans.push_back({v, f});
                }
                fi -= f;
                encoded2[j][1] -= f;
                if (encoded2[j][1] == 0) {
                    ++j;
                }
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
func findRLEArray(encoded1 [][]int, encoded2 [][]int) (ans [][]int) {
    j := 0
    for _, e := range encoded1 {
        vi, fi := e[0], e[1]
        for fi > 0 {
            f := min(fi, encoded2[j][1])
            v := vi * encoded2[j][0]
            if len(ans) > 0 && ans[len(ans)-1][0] == v {
                ans[len(ans)-1][1] += f
            } else {
                ans = append(ans, []int{v, f})
            }
            fi -= f
            encoded2[j][1] -= f
            if encoded2[j][1] == 0 {
                j++
            }
        }
    }
    return
}

评论