含None值矩阵的排序与行插入优化：处理独立列及组合规则

每行至少包含两个数字，其余列为None，需将矩阵排序满足以下规则：

1. 每列按递增顺序排列，允许数字间存在None；
2. 每列中每个数字仅出现一次；
3. 若两行在某一列有相同数字且无冲突值，需合并为一行。

有效/无效合并示例 #

• 有效组合：[1, 2, None, None]与[None, 2, 3, None]可合并为[1, 2, 3, None]，因第二列共享值2且无冲突。
• 无效组合：
  • [1, 2, None, None]与[None, None, 3, 4]无共享数字，无法合并；
  • [1, 2, None, None]与[2, 2, None, None]第一列值冲突，无法合并。

最终矩阵需满足：每列数字不重复、列递增，若无法实现则返回False。

问题场景示例 #

现有矩阵：

matrix = [
    [1, 2, None, None],
    [None, None, 3, 4],
    [3, 5, None, None]
]

插入新行：

new_row = [None, 1, 6, None]

现有算法检查新行数字的允许范围，发现1只能插在第一行上方，6只能插在第二或第三行之后，因无范围重叠判定无法插入，但重新排列矩阵后可实现插入。

现有实现逻辑 #

现有方法假设输入已排序矩阵，插入新行时需维持列递增、列内数字唯一、重叠数字同行的规则，步骤如下：

1. 检查新行数字是否已在对应列出现，若已出现则需插入到对应行；
2. 若未出现，确定每个数字的允许插入范围，找所有范围的重叠区，有则插入；
3. 无重叠则返回False。

待优化方向 #

1. 如何优化行插入或矩阵排序逻辑，以稳健处理此类情况？
2. 有哪些数学概念或算法可用于优化方案，尤其是识别矩阵中的独立列区块？

内容的提问来源于stack exchange，提问作者ykerman