找到数组中第二大元素,并进行最少的比较

Question

对于大小为N的数组,所需的比较数是多少？

Answer 1

最优算法使用n + log n-2比较.将元素视为竞争对手,锦标赛将对其进行排名.

首先,比较元素,如在树中

   |
  / \
 |   |
/ \ / \
x x x x

这需要进行n-1次比较,每个元素在最多log n次时进行比较.你会发现最大的元素是胜利者.

第二大元素必须与胜利者失去一场比赛(他不能失去与另一个元素的比赛),所以他是胜利者对阵的对手之一.您可以使用log n-1比较找到它们中的哪一个.

通过对手论证证明了最优性.请参阅https://math.stackexchange.com/questions/1601或http://compgeom.cs.uiuc.edu/~jeffe/teaching/497/02-selection.pdf或 http://www.imada.sdu. dk/~jbj/DM19/lb06.pdf或https://www.utdallas.edu/~chandra/documents/6363/lbd.pdf

Answer 2

您可以找到第二大值,最多2·(N -1)个比较,以及两个包含最大和第二大值的变量:

largest := numbers[0];
secondLargest := null
for i=1 to numbers.length-1 do
    number := numbers[i];
    if number > largest then
        secondLargest := largest;
        largest := number;
    else
        if number > secondLargest then
            secondLargest := number;
        end;
    end;
end;

Answer 3

使用冒泡排序或选择排序算法,按降序对数组进行排序.不要完全排序数组.只需两次通过.第一遍给出最大元素,第二遍给你第二大元素.

第一次通过的比较次数:n-1

第一次通过的比较次数:n-2

总数没有.寻找第二大的比较:2n-3

也许你可以推广这个算法.如果您需要第3大,那么您将获得3次通过.

通过上面的策略,您不需要任何临时变量,因为冒泡排序和选择排序就位排序算法.