时间复杂度最优的独属子数组索引查找函数实现方案

核心思路 #

要解决这个问题，我们必须先掌握每个数字在哪些子数组中出现，再反过来验证每个子数组的所有数字是否仅属于自身。由于必须遍历所有元素一次才能获取完整的数字分布信息，O(N)是理论上的最优时间复杂度，无法再进一步压缩。

具体实现步骤 #

1. 构建数字-所属子数组索引映射

   • 创建一个哈希表（比如Python中的字典）num_to_indices，键是数字，值是该数字出现过的子数组索引的集合（用集合是为了自动去重，同一个数字在同一子数组中多次出现只记录一次索引）。
   • 遍历每个子数组的索引i，再逐个遍历子数组里的数字num：
     • 把i加入num_to_indices[num]对应的集合中（如果num不在字典里，先初始化一个空集合）。
   • 这一步每个元素只处理一次，集合的添加操作平均时间为O(1)，总耗时O(N)。

2. 筛选符合条件的子数组索引

   • 再次遍历每个子数组的索引i和对应的子数组sub_arr：
     • 检查子数组里的每一个数字num：确认num_to_indices[num]的大小为1，且集合里的唯一元素就是i。
     • 如果子数组中所有数字都满足这个条件，那么i就是我们要找的索引。
   • 这一步同样是遍历所有元素一次，总耗时O(N)。

示例验证 #

拿题目中的输入L = [[1, 2, 3], [1, 2], [1, 2, 3, 5, 6, 8], [1, 8, 6, 10, 21], [1, 4, 6, 9], [22]]来说：

• 统计后，num_to_indices[22] = {5}，而数字1对应的集合是{0,1,2,3,4}，数字2对应的是{0,1,2}，以此类推。
• 检查索引5的子数组[22]：数字22的索引集合大小为1且等于5，符合条件；其他子数组都存在至少一个数字出现在多个子数组中，所以最终只有索引5符合要求。

关键细节 #

• 子数组内的重复数字不影响判断，比如[22,22]这种情况，只要22只在这个子数组里，就符合条件。
• 用集合记录索引可以避免同一子数组内重复数字的冗余记录，减少后续检查的工作量。

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