搜索未排序的数组

Question

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

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

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

Answer 1

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

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

最好的情况 - 你在第一次比较时找到它(假设你只需要找到一个)。

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

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