Question

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

English Version

题目描述

行程编码（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)$。

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

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;
  }
}

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;
  }
};

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
}