05 August 2008
Run-length encoding游程编码是一种压缩算法，它允许具有许多连续重复数字段的整数数组 nums 由编码的（通常较小的）二维数组表示。每个 encoded[i] = [vali, freqi] 描述了以 nums 为单位的重复数字的第 i 段，其中 vali 是重复 freqi 次的值。
例如，nums = [1,1,1,2,2,2,2,2] 由运行长度编码数组编码 = [[1,3],[2,5]] 表示。另一种解读方式是“三个 1 后跟五个 2”。 可以使用以下步骤计算两个行程编码数组编码1和编码2的乘积：
将encoded1 和encoded2 分别展开为完整的数组nums1 和nums2。 创建一个长度为 nums1.length 的新数组 prodNums 并设置 prodNums[i] = nums1[i] * nums2[i]。 将 prodNums 压缩成一个运行长度编码的数组并返回它。 给定两个游程编码数组encoded1 和encoded2，分别代表完整数组nums1 和nums2。 nums1 和 nums2 的长度相同。每个 encoded1[i] = [vali, freqi] 描述 nums1 的第 i 个片段，每个 encoded2[j] = [valj, freqj] 描述 nums2 的第 j 个片段。
返回编码1 和编码2 的乘积。
注意：应该进行压缩，以使游程编码的数组具有最小的可能长度。
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Solution {
/*
Don't calculate one by one, it will cause TLE
Instead, we need to use two pointer to track each element
If the current product is the same with prev-product, we will add the min-freq into count
otherwise, add the segement number into results
also, need to track if the both freq1 and freq2 are zero, once there equals zero, need to
move the pointer forward
*/
public List<List<Integer>> findRLEArray(int[][] e1, int[][] e2) {
int len1 = e1.length, len2 = e2.length;
List<List<Integer>> results = new ArrayList<>();
if (len1 == 0 && len2 == 0) {
return results;
}
int index1 = 0, index2 = 0;
int val1 = e1[index1][0], freq1 = e1[index1][1];
int val2 = e2[index2][0], freq2 = e2[index2][1];
int prevVal = val1 * val2;
int count = 0, currVal = 0;
while (index1 < len1 && index2 < len2) {
while (freq1 > 0 && freq2 > 0) {
currVal = val1 * val2;
int minFreq = Math.min(freq1, freq2);
if (currVal == prevVal) {
count += minFreq;
} else {
List<Integer> currList = new ArrayList<>();
currList.add(prevVal);
currList.add(count);
results.add(currList);
count = minFreq;
prevVal = currVal;
}
freq1 -= minFreq;
freq2 -= minFreq;
}
if (freq1 == 0 && index1 + 1 < len1) {
index1++;
val1 = e1[index1][0];
freq1 = e1[index1][1];
}
if (freq2 == 0 && index2 + 1 < len2) {
index2++;
val2 = e2[index2][0];
freq2 = e2[index2][1];
}
if (freq1 == 0 && freq2 == 0) break;
}
List<Integer> list = new ArrayList<>();
list.add(currVal);
list.add(count);
results.add(list);
return results;
}
}