难度: Medium
Submission
运行时间: 211 ms
内存: 67.1 MB
class Solution:
def findRLEArray(self, encoded1: List[List[int]], encoded2: List[List[int]]) -> List[List[int]]:
m, n = len(encoded1), len(encoded2)
curr, c = None, 0
i, j = 0, 0
res = []
while i < m and j < n:
count1, count2 = encoded1[i][1], encoded2[j][1]
num1, num2 = encoded1[i][0], encoded2[j][0]
if count1 < count2:
i += 1
count = count1
encoded2[j][1] -= count
elif count1 > count2:
j += 1
count = count2
encoded1[i][1] -= count
else:
i += 1
j += 1
count = count1
prod = num1 * num2
if not curr:
curr, c = prod, count
else:
if prod != curr:
res.append([curr, c])
curr, c = prod, count
else:
c += count
res.append([curr, c])
return res
Explain
此题解的核心思路是将两个行程编码数组（每个数组中的元素由[value, count]组成，表示value出现count次）进行逐对元素的乘积，并且保持行程编码的形式。算法逐一比较两个数组中的当前元素，计算乘积，并更新计数。如果两数组当前元素的计数不一致，则减少计数较小的数组的当前元素的计数，并将其指针前移，否则同时前移两数组的指针。当两数组相应计数的乘积与之前的乘积相同，合并计数；否则，将当前乘积和计数作为新的元素添加到结果数组中。
时间复杂度: O(m+n)
空间复杂度: O(m+n)
class Solution:
def findRLEArray(self, encoded1: List[List[int]], encoded2: List[List[int]]) -> List[List[int]]:
m, n = len(encoded1), len(encoded2) # 获取两个数组的长度
curr, c = None, 0 # 初始化当前乘积和计数
i, j = 0, 0 # 初始化两个数组的索引
res = [] # 初始化结果数组
while i < m and j < n: # 当两个索引都未越界时
count1, count2 = encoded1[i][1], encoded2[j][1] # 获取当前元素的计数
num1, num2 = encoded1[i][0], encoded2[j][0] # 获取当前元素的值
if count1 < count2: # 当第一个数组的计数较小
i += 1
count = count1
encoded2[j][1] -= count # 更新第二个数组的当前元素计数
elif count1 > count2: # 当第二个数组的计数较小
j += 1
count = count2
encoded1[i][1] -= count # 更新第一个数组的当前元素计数
else: # 当两个数组的计数相等
i += 1
j += 1
count = count1 # 设置计数为当前计数
prod = num1 * num2 # 计算当前元素的乘积
if not curr: # 如果没有当前乘积
curr, c = prod, count # 设置当前乘积和计数
else:
if prod != curr: # 如果新的乘积与当前乘积不同
res.append([curr, c]) # 将当前乘积和计数添加到结果数组
curr, c = prod, count # 更新当前乘积和计数
else: # 如果新的乘积与当前乘积相同
c += count # 累加计数
res.append([curr, c]) # 添加最后一个乘积和计数到结果数组
return res # 返回结果数组
Explore
这种处理方式确保了算法的正确性，因为它允许两个数组中对应的元素按照实际出现的次数进行乘积运算。当一个数组的当前元素的计数小于另一个数组时，通过减少等量的计数并前移指针，可以确保每个元素都被完全且正确地处理，而不会有遗漏或重复。此操作保证了两个数组的元素在运算中的对应性，使得最终的行程编码数组能准确反映出所有可能的乘积及其出现次数。
选择累加计数而非立即产生新的结果元素可以有效减少结果数组的大小，从而优化存储空间的使用。在行程编码中，相同值的连续出现可以合并为一个元素，减少了数组的元素数量，提高了空间效率。此外，这种做法还减少了数组操作的次数，可能对算法的运行时间也有一定的优化效果。
算法的这一处理确实考虑到了所有边界情况。由于在每次循环中，只有在当前乘积发生变化时才会将之前的乘积与计数存入结果数组，而最后一组乘积和计数在循环结束时可能尚未被添加。因此，在循环结束后直接添加最后一组乘积和计数确保了包括最后一次计算在内的所有乘积都被正确记录。
在题目的上下文中，一旦一个数组遍历完成，另一个数组中剩下的元素实际上不需要再处理，因为行程编码表示的是有限的元素和其出现次数。如果其中一个数组已经处理完毕，意味着没有更多的元素来与另一个数组中的剩余元素相乘。因此，这种情况下，算法不需要对剩余的元素进行额外的处理，直接结束即可。