时间戳

首页 > 解决方案 > 使用最多 3/2n 比较找到数组中两个元素之间的最大差异

algorithm - 使用最多 3/2n 比较找到数组中两个元素之间的最大差异

问题描述

我正在处理一个带有整数元素的未排序数组，

A={a_1,a_2,...,a_n}

找到数组中两个元素之间的最大差异（在最坏的情况下max|a_i-a_j|)最多使用3/2n比较。（运行时无关紧要，我们不能使用诸如 max 或 min 之类的操作）。

我真的怀疑这是否可能：要找到两个元素的最大差异，在最坏的情况下，我们不应该总是需要2n比较，因为我们需要使用大约 n 个比较来找到数组的最大元素和另一个 n比较以找到数组的最小元素？我不知道在哪里可以削减操作。

我也考虑过分而治之。假设我将这个数组分成 2 个长度为的子数组n/2，但后来我遇到了同样的问题，因为在每个子数组中找到最大值和最小值并进行n比较，所以总共会有2n比较。

关于如何做到这一点的提示将不胜感激。

标签： algorithmmax

解决方案

很简单，找到最大差异等于找到数组元素的最小值和最大值。另一方面，您可以通过比较同时找到数组的最小值和最大值3n/2（所有常见编程语言中的第三种方法，即 C#、C++、Python、C 和 Java）：

如果 n 是奇数，则将 min 和 max 初始化为第一个元素。

如果 n 是偶数，则将 min 和 max 分别初始化为前两个元素的最小值和最大值。

对于其余元素，成对挑选它们并将它们的最大值和最小值分别与最大值和最小值进行比较。

比较总数：偶数和奇数 n 不同，见下文：

 If n is odd:    3*(n-1)/2  
 If n is even:   1 Initial comparison for initializing min and max, 
                      and 3(n-2)/2 comparisons for rest of the elements  
                 =  1 + 3*(n-2)/2 = 3n/2 -2

推荐阅读