通过最多1.5n比较来查找高/低数字的算法 [英] Algorithm to find high/low numbers with at most 1.5n comparisons

问题描述

我一直在思考这个家庭作业问题。给定大小为n的数字数组，设计一种算法，该算法最多可以找到1.5n个比较值。

I've been thinking about this homework question for a bit now. Given an number array of size n, design an algorithm that will find the high and and low values with at most 1.5n comparisons.

我的第一次尝试是

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]

}

我的问题是循环的每次迭代都有以下三种可能性之一：

My problem is each iteration of the loop has one of three possibilities:

• 发现低值-进行了1次比较


• 发现了高值-2次进行了比较


• 未找到-进行了2次比较

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

So for an entire array traversal, a maximum of 2n comparisons can be made, which is a far cry from the problem maximum requirement of 1.5n comparisons.

推荐答案

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

Start with a pairs of numbers and find local min and max (n/2 comparisons). Next, find global max from n/2 local maxes (n/2 comparisons), and similarly global min from local mins (n/2 comparisons). Total comparisons: 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

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

Note that the above solution changes the array. Alternate solution:

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]

这篇关于通过最多1.5n比较来查找高/低数字的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！