如何高效判断列表集合是否存在极小列表？无需遍历所有列表对

当然有不用遍历所有列表对的高效方法，核心思路是先筛选出唯一可能的候选极小列表，再验证这个候选是否符合要求，整体时间复杂度为O(n*d)（n是列表数量，d是每个列表的维度），远低于遍历所有列表对的O(n²*d)。

具体步骤 #

1. 筛选候选极小列表

   • 从集合S中任选一个列表作为初始候选（比如第一个列表）。
   • 遍历S中剩余的每个列表y：
     • 如果y的所有元素都小于等于当前候选的对应元素：直接把候选替换成y（y比当前候选更“小”，更有资格成为全局极小）。
     • 如果候选和y互相不支配（即y既有元素比候选大，也有元素比候选小）：保留当前候选（此时两者都不可能成为对方的极小，但候选仍有机会成为全局极小）。
     • 如果候选的所有元素都小于等于y的对应元素：直接跳过y（y不可能是全局极小，无需关注）。

2. 验证候选是否为真正的极小列表

   • 遍历整个集合S，检查候选的每个位置元素是否都小于等于其他所有列表的对应元素。
   • 如果全部满足，说明S存在极小列表；如果有任何一个列表不满足，说明S不存在极小列表。

示例演示 #

示例1：存在极小列表的情况

S = [[4, 5, 6], [3, 6, 9], [1, 4, 6], [2, 5, 8]]

• 初始候选：[4,5,6]
• 遍历[3,6,9]：两者互相不支配，候选保留[4,5,6]
• 遍历[1,4,6]：1≤4，4≤5，6≤6，所有元素都≤候选，候选替换为[1,4,6]
• 遍历[2,5,8]：候选所有元素都≤该列表，候选不变
• 验证候选：检查所有列表，[1,4,6]的每个元素都≤其他列表对应位置，确认存在极小列表。

示例2：不存在极小列表的情况

S = [[4, 5], [3, 6]]

• 初始候选：[4,5]
• 遍历[3,6]：两者互相不支配，候选保留[4,5]
• 验证候选：检查[3,6]时，4>3，不满足“候选元素均不大于对应位置”，因此S不存在极小列表。

方法原理 #

这个方法之所以不用遍历所有列表对，是因为我们通过一次遍历就排除了所有不可能成为全局极小的列表，最终只需要验证一个候选——如果连这个最“小”的候选都不满足条件，那集合里不可能存在任何极小列表；如果满足，那它就是我们要找的极小列表。

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