表格合并分组算法

Question

现在有这样一个需求，一列中相邻行的值相同进行合并，但合并必须是在前一个字段的集合下合并。
如上：B列，按照相邻行相同字段进行合并，此时合并为B组和BB组两个分组。
C列，前三行在B组的集合下可以分为 C组和CC组 后四行在BB组的集合下分为C组，CD组，CCC组三组
以此类推…,后面所有分组依赖于前一个列的分组数据。
就此，想请教一下怎么去实现这个需求。我只能想到是一个树形结构，但如果列数较多是否层级会很深。

最后想要的结果如下图

节点里面的数字代码这个节点下有多少条数据，其实就是每个子节点寻找相同是必须在父节点的数据集，而不是list整个数据中去找。

Answer 1

liuyubobobo 2022-06-22 10:32:43

其实我没有理解这个问题。请你对于一个例子给我两张截图，一张是合并前，一张是合并后，我再理解一下规则。

但不管怎样，对于“如果列数较多是否层级会很深”这个问题，那是当然。对于处理一个表格（或者一个文本，或者一个文件，等等等等）的算法，一般情况下最好也是 O(n) 的。也就是你的算法需要掌握这个文件中的所有信息，才能做出适当的处理。而“掌握这个文件的所有信息”本身就是 O(n) 的。（除非你的信息流中存在某种标记，可以让算法跳过很多信息做处理。）

所以如果你想到的算法复杂度比 O(n) 高，可以思考有没有可能向 O(n) 靠拢。否则的话，进一步优化的方式是在文件组织上，有没有可能提供给算法更多信息，让算法能够省略一些信息作出判断。如果你考量的是因为深度所以递归算法会导致系统的栈空间不够的话，所有的递归算法都可以改写成非递归算法。

继续加油！：）

• 提问者 慕UI2478098 #1

  我更新了一下想要的结果如上树形图，不知是否能读懂我想表达的想法。

• liuyubobobo 回复 提问者 慕UI2478098 #2

  其实还是有具体的规则我没有很明确。但是如果我没有理解错，整体就是根据这个 table 中的数据建立这样一棵树，时间复杂度至少是这个 table 中的 cell 数的，即 O(n) 的。就是因为每一个节点只会考虑其“子节点”（而不是整个表中的其他所有节点），才可能是 O(n) 的，否则是 O(n^2) 的（即对于每个节点，都要看整个表格中的所有其他元素）。