也可能具有重复元素的未排序数组中的最小和最大比较次数是多少？
我知道在未排序的数组中查找任何内容都是 O(n) 问题。但是，如果数组也包含重复元素，这是真的吗？
我所说的重复元素是指在给定数组中多次出现的元素。
所以这里的想法是你必须从头到尾遍历数组，因为它是未排序的。这意味着您正在查看 O(n) - 元素的线性遍历。无论您要搜索的位置是在位置 0、位置 8 还是位置 n-1，您都必须遍历数组才能找到它。
现在，如果数组中可能存在重复项，唯一的区别是您可能会找到该值的多个实例。如果您要查找所有这些或仅查找第一个，它仍然是 O(n) 的情况。重复项不会改变复杂性。
最好的情况 - 您在第一次比较时找到它（假设您只需要找到一个）。
最坏的情况 - 给定值没有重复项，并且这是您检查的最后一个 - 第 n 次比较。
如果您必须找到所有重复项，则始终需要进行 n 次比较，因为您必须访问未排序数组中的每个元素。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
