问题由两个排序列表组成，没有重复项，大小为 n 和 m。第一个列表包含应从第二个列表中删除的字符串。
最简单的算法必须执行 nxm 操作(我相信这个术语是“二次时间”？)。
改进的解决方案是利用两个列表都已排序的事实，并在以后的比较中跳过索引低于上次删除索引的字符串。 我想知道那是什么时间复杂度？
这个问题有没有时间复杂度更好的解决方案？
最佳答案
你应该看看Merge sort .这就是它高效工作背后的基本思想。
想法是同时扫描两个列表，这需要 O(n+m)时间:
制作指针x对于第一个列表，说 A和另一个指针 y对于第二个列表，说 B .设置x=0和 y=0 .同时 x < n和 y < m , 如果 A[x] < B[y] , 然后添加 A[x]到新的合并列表并递增 x .否则添加 B[y]到新列表并增加 y .一旦你点击 x=n或 y=m , 接受 B 中的剩余元素或 A , 分别。
关于algorithm - 从列表中删除项目 - 算法时间复杂度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/11234078/