文章/答案/技术大牛

发布

社区首页 >问答首页 >Array - Dupe扫描器与算法的运行时间

问Array - Dupe扫描器与算法的运行时间
EN

Stack Overflow用户

提问于 2016-04-27 02:37:12

回答 1查看 36关注 0票数 1

我有两个任务要做：

1.)创建一个算法，以便它检测数组中是否有重复(=相同的数字)(它的运行时间越好，我得到的分数就越多)。

2.)分析你的算法的运行时。

这是我的第一个任务的代码(我必须对数组进行排序，这样算法才能更快地工作。为此，我使用import而不是自己编写代码。)：

import java.util.Arrays;

public class Dupescanner
{
    public static void main(String[] args)
    {
        int[] A = {1, 2, 3, 4, 5, 1, 2, 8, 8};
        Arrays.sort(A);
        System.out.println("Following numbers are duplicates:");
        for (int n = 1; n < A.length; n++)
        {
            if (A[n] == A[n - 1])
            {
                System.out.println(A[n]);
            }
        }
    }
}

输出：

Following numbers are duplicates:
1
2
8

这个算法很好吗？我想不出比这更快的了。或者，也许我误解了这个任务，如果你只是说:真的--有/有重复的，那就足够了。假-不是..。

对于运行时分析，我不确定，但我也尝试了一下：

int[] A = {1, 2, 3, 4, 5, 1, 2, 8, 8};

成本1

for循环的开销是n，if的开销也是n。结果将是n^2 + 1。而且我不确定数组排序是否算数，我排除了它。

runtime

java

algorithm

回答 1

Stack Overflow用户

发布于 2016-04-27 02:48:45

你的算法是O(nlogn)，这里的瓶颈是排序。

你的循环在线性时间内运行。

这实际上是element distinctness problem。

只有在允许哈希和额外空间的情况下，通过填充哈希表(HashSet)，并在迭代时将所有元素插入其中，如果您在迭代时找到一个副本-打印它，才能更有效地解决这个问题(就渐近复杂性而言)。

int[] array = {1, 2, 3, 4, 5, 1, 2, 8, 8};
Set<Integer> set = new HashSet<>();
System.out.println("Following numbers are duplicates:");
for (int e : array) { 
  if (!set.add(e)) System.out.println("" + e);
}

This thread讨论了问题的下界。

票数 2

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/36873152

复制

相似问题

问Array - Dupe扫描器与算法的运行时间
EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问Array - Dupe扫描器与算法的运行时间EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问Array - Dupe扫描器与算法的运行时间
EN