搜索未排序的数组 [英] Searching an unsorted array

问题描述

在未排序的数组中也可能有重复元素的最小和最大比较数是多少？

What would be the smallest and largest number of comparisons in an unsorted array that could have duplicate elements as well ?

我知道在未排序的数组中查找任何内容都是O（n）问题。但是，如果数组也包含重复元素，这是真的吗？

I understand that finding anything in an unsorted array is a O(n) problem. But, is this true if the array contains duplicate elements as well ?

我所说的重复元素是指在给定数组中出现多次的元素。

By duplicate elements I mean, elements that occur more than once in the given array.

推荐答案

所以这里的想法是，由于数组未排序，因此必须从头到尾遍历。这意味着您正在查看O（n）-元素的线性遍历。无论您要搜索的是位于位置0，位置8还是位置n-1，都必须遍历数组以查找它。

So the idea here is that you've got to walk the array from front to end because it is unsorted. That means you're looking at O(n) - a linear traversal of the elements. Regardless of whether the one you are searching for is at position 0, position 8, or position n-1, you've got to walk the array to find it.

现在，如果数组中可能存在重复项，则唯一的区别是您可能会发现该值的多个实例。如果您正在寻找所有这些，或者只是寻找第一个，那么仍然是O（n）的情况。重复项不会改变复杂性。

Now, if there are possibly duplicates in the array, the only difference is that you may find more than one instance of the value. If you are looking for all of them or just the first one, it is still a O(n) situation. The duplicates don't change the complexity.

最好的情况-您可以在第一次比较中找到它（假设只需要找到一个）。

Best case - you find it (assuming you only need to find one) on the first comparison.

最糟糕的情况-给定值没有重复项，它是您检查的最后一个-第n个比较。

Worst case - there are no duplicates for the given value and it is the last one you check - the nth comparison.

如果必须找到所有重复项，它总是要进行n次比较，因为您必须访问未排序数组中的每个元素。

If you had to find ALL of the duplicates, it is always going to be n comparisons, because you've got to visit each element in the unsorted array.

这篇关于搜索未排序的数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！