查找最多1.5n比较的高/低数字的算法

Question

我一直在考虑这个作业问题。给定一个大小为n的数组，设计一个算法，可以在最多1.5n的比较中找到高值和低值。

我的第一次尝试是

int high=0 
int low= Number.MaxValue //problem statement is unclear on what type of number to use 
Number numList[0 . . n] //number array, assuming unsorted 

for (i=0, i < n, i++) { 
    if (numList[i] > high) 
    high = numList[i] 

    else if (numList[i] < low) 
    low = numList[i] 

} 

我的问题是在每次循环有以下三种可能性：

• 低价值发现 - 1相比是
• 高价值发现 - 进行了2次比较
• 均未找到 - 进行了2次比较

因此，对于整个数组遍历，最多可以进行2n次比较，这与1.5n比较的最大问题的要求相差甚远。

Answer 1

从一对数字开始，找到局部最小和最大（n/2比较）。接下来，从n/2局部最大值（n/2比较）中找到全局最大值，并从局部分钟（n/2比较）中找到类似的全局最小值。总比较：3 * n/2！

For i in 0 to n/2: #n/2 comparisons 
    if x[2*i]>x[2*i+1]: 
     swap(x,2*i,2*i+1) 

global_min = min(x[0], x[2], ...) # n/2 comparisons 
global_max = max(x[1], x[3], ...) # n/2 comparisons 

请注意，上述解决方案更改数组。替代解决方案：

Initialize min and max 
For i = 0 to n/2: 
    if x[2*i]<x[2*i+1]: 
     if x[2*i]< min: 
      min = x[2*i] 
     if x[2*i+1]> max: 
      max = x[2*i+1] 
    else: 
     if x[2*i+1]< min: 
      min = x[2*i+1] 
     if x[2*i]> max: 
      max = x[2*i] 

Answer 2

这与ElKamina的答案相同，但由于我已经开始编写伪代码，所以我认为我会完成并发布它。

这个想法是比较对值（n/2比较）对以获得高值数组和低值数组。对于每个数组，我们再次比较数值对（2 * n/2比较）以分别获得最高值和最低值。

n/2 + 2*n/2 = 1.5n comparisons 

这里是伪代码：

int[] highNumList; 
int[] lowNumList; 

for (i = 0, i < n, i+=2) 
{ 
    a = numList[i]; 
    b = numList[i+1]; 
    if (a > b) 
    { 
     highNumList.Add(a); 
     lowNumlist.Add(b); 
    } 
    else 
    { 
     highNumlist.Add(b); 
     lowNumList.Add(a); 
    } 
} 

int high = highNumList[0]; 
int low = lowNumList[0]; 

for (i = 0, i < n/2, i+=2) 
{ 
    if (highNumList[i] < highNumList[i+1]) 
     high = highNumList[i+1] 
    if (lowNumList[i] > lowNumList[i+1]) 
     low = lowNumList[i+1] 
} 

此代码不占n不是偶数或初始数组为空。

Answer 3

这是我在面试过程中遇到的一个问题，我从面试官那里得到了一个小小的提示：“你如何比较两个号码？” （它确实有帮助）。

这里的解释是：

可以说我有100个号码（你可以很容易地被N取代它，但它的工作的例子更好，如果n为偶数）。我所做的是我将它分成50个2个数字的列表。对于每一对我做一个比较，我完成了（现在做50比较），那么我只需要找到最小值（这是49比较）和最大值的最大值（这也是49比较以及），这样我们必须做出49 + 49 + 50 = 148的比较。我们完成了！

备注：找我们进行如下（在伪代码）的最小值：

n=myList.size(); 
    min=myList[0]; 
    for (int i(1);i<n-1;i++) 
    { 
    if (min>myList[i]) min=myList[i]; 
    } 
    return min; 

而且我们发现它在（N-1）的比较。代码的最大值几乎相同。

Answer 4

我知道这已经得到了回答，但如果有人正在寻找另一种方式来思考这一点。这个答案与Lester's类似，但可以处理n的奇数值而不会中断，并且仍然可以进行至多1.5n的比较。秘密在于模数。 ;）

作为确保我们将最后一个值放在正确的子数组中的副作用，givenList中的第二个元素将进行比较并放置两次。但是，由于我们没有改变原始数组，所以我们只对该组的高和低有兴趣，这并没有真正的区别。

Initialize lowArray and highArray 
Initialize subArrayCounter to 0 

For i = 0; i < n; i+=2 
    X = givenList[i]; 
    Y = givenList[(i+1)%n]; 
    If(x < y) 
     lowArray[subArrayCounter] = x; 
     highArray[subArrayCounter] = y; 
     subArrayCounter++; 
    else 
     lowArray[subArrayCounter] = y; 
     highArray[subArrayCounter] = x; 
     subArrayCounter++; 

Initialize low to lowArray[0]; 
Initialize high to highArray[0]; 

For i = 1; i < lowArray.length; i++ 
    If(lowArray[i] < low) 
     Low = lowArray[i]; 

For i = 1; i < highArray.length; i++ 
    If(highArray[i] > high) 
     High = highArray[i]