c - 使用分而治之法检测重复项 - 归并排序

Question

我想使用分治法检测给定数组中的重复项。我可以为此使用合并排序吗:

1. 首先将数组拆分为 log N 步

2. 然后合并排序

3. 合并时使用计数器变量检测重复项。 O(N)

所以总共需要 O(N log N) 步...

这种方法是否正确？

Answer 1

你不需要。你可以在 O(n) 中完成

你有原始数组 int A[N];同样创建第二个数组 bool a[N]，类型为 bool=false。迭代第一个数组并设置 a[A[i]]=true 如果它是 false，否则你找到了一个重复项。