找到数组中第二大的元素，并使用最少的比较次数

你可以找到最多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;

将数组按升序排序，然后将一个变量赋给(n-1)第三个项。

假设空间是无关紧要的，这是我能得到的最小的空间。在最坏的情况下需要2 * n 的比较，在最好的情况下需要 n 的比较:

arr = [ 0, 12, 13, 4, 5, 32, 8 ]
max = [ -1, -1 ]


for i in range(len(arr)):
if( arr[i] > max[0] ):
max.insert(0,arr[i])
elif( arr[i] > max[1] ):
max.insert(1,arr[i])


print max[1]

最优算法使用 n + log n-2比较，把元素看作竞争对手，比赛将对它们进行排名。

首先，比较元素，就像在树中一样

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

这需要进行 n-1比较，并且每个元素在大多数 log n 次中都要参与比较。你会发现最大的元素作为赢家。

第二大元素一定是输给了赢家(他不能输给另一个元素) ，所以他是赢家所对抗的 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

下面是一些可能不是最优的代码，但至少实际上找到了第二大元素:

if( val[ 0 ] > val[ 1 ] )
{
largest = val[ 0 ]
secondLargest = val[ 1 ];
}
else
{
largest = val[ 1 ]
secondLargest = val[ 0 ];
}


for( i = 2; i < N; ++i )
{
if( val[ i ] > secondLargest )
{
if( val[ i ] > largest )
{
secondLargest = largest;
largest = val[ i ];
}
else
{
secondLargest = val[ i ];
}
}
}

如果最大的2个元素位于数组的开头，那么至少需要进行 N-1比较，而在最坏的情况下最多需要进行2N-3比较(前2个元素中的一个是数组中最小的)。

案例1—— > 987654321
案例2—— > 5010825..。
案例3—— > 505010825..。
案例4—— > 50501085025。

public void second element()
{
int a[10],i,max1,max2;
max1=a[0],max2=a[1];
for(i=1;i<a.length();i++)
{
if(a[i]>max1)
{
max2=max1;
max1=a[i];
}
else if(a[i]>max2 &&a[i]!=max1)
max2=a[i];
else if(max1==max2)
max2=a[i];
}
}

使用计数排序，然后找到第二个最大的元素，从索引0开始一直到结束。至少应该有1个比较，最多 n-1(当只有一个元素时!).

试试这个。

max1 = a[0].
max2.
for i = 0, until length:
if a[i] > max:
max2 = max1.
max1 = a[i].
#end IF
#end FOR
return min2.

应该很有效，复杂度低。

这是 Java 代码。

int secondlLargestValue(int[] secondMax){
int max1 = secondMax[0]; // assign the first element of the array, no matter what, sorted or not.
int max2 = 0; // anything really work, but zero is just fundamental.
for(int n = 0; n < secondMax.length; n++){ // start at zero, end when larger than length, grow by 1.
if(secondMax[n] > max1){ // nth element of the array is larger than max1, if so.
max2 = max1; // largest in now second largest,
max1 = secondMax[n]; // and this nth element is now max.
}//end IF
}//end FOR
return max2;
}//end secondLargestValue()

#include<stdio.h>
main()
{
int a[5] = {55,11,66,77,72};
int max,min,i;
int smax,smin;
max = min = a[0];
smax = smin = a[0];
for(i=0;i<=4;i++)
{
if(a[i]>max)
{
smax = max;
max = a[i];
}
if(max>a[i]&&smax<a[i])
{
smax = a[i];
}
}
printf("the first max element z %d\n",max);
printf("the second max element z %d\n",smax);
}

抱歉 JS 代码。

通过两个输入进行测试:

a = [55,11,66,77,72];
a = [ 0, 12, 13, 4, 5, 32, 8 ];


var first = Number.MIN_VALUE;
var second = Number.MIN_VALUE;
for (var i = -1, len = a.length; ++i < len;) {
var dist = a[i];
// get the largest 2
if (dist > first) {
second = first;
first = dist;
} else if (dist > second) { // && dist < first) { // this is actually not needed, I believe
second = dist;
}
}


console.log('largest, second largest',first,second);
largest, second largest 32 13

这应该有一个最大的 a.length * 2比较，并且只通过列表一次。

使用气泡排序或选择排序算法，按降序排序数组。不要对数组进行完全排序。只有两次机会。第一次传递给出最大的元素，第二次传递给出第二大元素。

首次比较次数: n-1

第二次比较次数: n-2

找到第二大的比较总数: 2n-3

也许你可以推广这个算法，如果你需要第三个最大的，那么你可以通过3次。

根据以上策略，你不需要任何临时变量，因为冒泡排序和选择排序是 就位分类算法。

我知道这是一个老问题，但这里是我尝试解决它，利用锦标赛算法。它类似于@sdcvvc 使用的解决方案，但是我使用二维数组来存储元素。

为了让事情顺利进行，有两个假设:
1)数组中元素的个数是2的幂
2)数组中没有副本

整个过程包括两个步骤:
1.通过比较两个元素来建立一个二维数组。二维数组中的第一行是整个输入数组。下一行包含前一行的比较结果。我们继续对新构建的数组进行比较，并继续构建2D 数组，直到达到只有一个元素(最大的元素)的数组。
2.我们有一个2D 数组，其中最后一行只包含一个元素: 最大的一个。我们继续从底部到顶部，在每个数组中找到被最大的元素“击败”的元素，并将其与当前的“第二大”值进行比较。为了找到被最大元素击败的元素，并避免 O (n)比较，我们必须存储前一行中最大元素的索引。这样我们可以很容易地检查相邻的元素。在任何级别(在根级别之上) ，相邻元素按以下方式获得:

leftAdjacent = rootIndex*2
rightAdjacent = rootIndex*2+1,

其中 rootIndex 是上一级中最大(根)元素的索引。

我知道这个问题需要 C + + ，但是这里我尝试用 Java 来解决它。(我使用了列表而不是数组，以避免混乱地改变数组大小和/或不必要的数组大小计算)

public static Integer findSecondLargest(List<Integer> list) {
if (list == null) {
return null;
}
if (list.size() == 1) {
return list.get(0);
}
List<List<Integer>> structure = buildUpStructure(list);
System.out.println(structure);
return secondLargest(structure);


}


public static List<List<Integer>> buildUpStructure(List<Integer> list) {
List<List<Integer>> newList = new ArrayList<List<Integer>>();
List<Integer> tmpList = new ArrayList<Integer>(list);
newList.add(tmpList);
int n = list.size();
while (n>1) {
tmpList = new ArrayList<Integer>();
for (int i = 0; i<n; i=i+2) {
Integer i1 = list.get(i);
Integer i2 = list.get(i+1);
tmpList.add(Math.max(i1, i2));
}
n/= 2;
newList.add(tmpList);
list = tmpList;
}
return newList;
}


public static Integer secondLargest(List<List<Integer>> structure) {
int n = structure.size();
int rootIndex = 0;
Integer largest = structure.get(n-1).get(rootIndex);
List<Integer> tmpList = structure.get(n-2);
Integer secondLargest = Integer.MIN_VALUE;
Integer leftAdjacent = -1;
Integer rightAdjacent = -1;
for (int i = n-2; i>=0; i--) {
rootIndex*=2;
tmpList = structure.get(i);
leftAdjacent = tmpList.get(rootIndex);
rightAdjacent = tmpList.get(rootIndex+1);
if (leftAdjacent.equals(largest)) {
if (rightAdjacent > secondLargest) {
secondLargest = rightAdjacent;
}
}
if (rightAdjacent.equals(largest)) {
if (leftAdjacent > secondLargest) {
secondLargest = leftAdjacent;
}
rootIndex=rootIndex+1;
}
}


return secondLargest;
}

C + + 11中 sdcvvc 接受的解决方案。

#include <algorithm>
#include <iostream>
#include <vector>
#include <cassert>
#include <climits>


using std::vector;
using std::cout;
using std::endl;
using std::random_shuffle;
using std::min;
using std::max;


vector<int> create_tournament(const vector<int>& input) {
// make sure we have at least two elements, so the problem is interesting
if (input.size() <= 1) {
return input;
}


vector<int> result(2 * input.size() - 1, -1);


int i = 0;
for (const auto& el : input) {
result[input.size() - 1 + i] = el;
++i;
}


for (uint j = input.size() / 2; j > 0; j >>= 1) {
for (uint k = 0; k < 2 * j; k += 2) {
result[j - 1 + k / 2] = min(result[2 * j - 1 + k], result[2 * j + k]);
}
}


return result;
}


int second_smaller(const vector<int>& tournament) {
const auto& minimum = tournament[0];
int second = INT_MAX;


for (uint j = 0; j < tournament.size() / 2; ) {
if (tournament[2 * j + 1] == minimum) {
second = min(second, tournament[2 * j + 2]);
j = 2 * j + 1;
}
else {
second = min(second, tournament[2 * j + 1]);
j = 2 * j + 2;
}
}


return second;
}


void print_vector(const vector<int>& v) {
for (const auto& el : v) {
cout << el << " ";
}
cout << endl;
}


int main() {


vector<int> a;
for (int i = 1; i <= 2048; ++i)
a.push_back(i);


for (int i = 0; i < 1000; i++) {
random_shuffle(a.begin(), a.end());
const auto& v = create_tournament(a);
assert (second_smaller(v) == 2);
}


return 0;
}

我已经阅读了以上所有的文章，但是我相信实现锦标赛算法是最好的方法。让我们考虑一下@Gumbo 发布的以下算法

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;

这是非常好的情况下，我们要找到一个数组中的第二大数。它有(2n-1)个比较。但是如果你想计算第三大数或者某个 kth 最大数。上述算法不起作用。你得去做另一个手术。

因此，我认为比赛算法是最好的方法，这里是 链接。

下面的解决方案将采取2(N-1)比较:

arr  #array with 'n' elements
first=arr[0]
second=-999999  #large negative no
i=1
while i is less than length(arr):
if arr[i] greater than first:
second=first
first=arr[i]
else:
if arr[i] is greater than second and arr[i] less than first:
second=arr[i]
i=i+1
print second

它可以在 n + ceil (log n)-2比较中完成。

解决方案: 需要 n-1比较才能得到最小值。

但为了获得最小值，我们将建立一个锦标赛，其中每个元素将成对分组。就像一个网球赛事，任何一轮的胜利者都会继续前进。

这棵树的高度将是 log n，因为我们每轮都要分成两半。

获得第二个最小值的想法是它将在前一轮中被最小值的候选人击败。因此，我们需要在潜在的候选人中找到最小值(被最小值击败)。

潜在的候选者将是 log n = tree 的高度

所以，使用竞赛树求最小值的比较次数是 n-1 第二个极小值是 log n-1 求和 = n + ceil (log n)-2

下面是 C + + 代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <vector>


using namespace std;


typedef pair<int,int> ii;


bool isPowerOfTwo (int x)
{
/* First x in the below expression is for the case when x is 0 */
return x && (!(x&(x-1)));
}
// modified
int log_2(unsigned int n) {
int bits = 0;
if (!isPowerOfTwo(n))
bits++;
if (n > 32767) {
n >>= 16;
bits += 16;
}
if (n > 127) {
n >>= 8;
bits += 8;
}
if (n > 7) {
n >>= 4;
bits += 4;
}
if (n > 1) {
n >>= 2;
bits += 2;
}
if (n > 0) {
bits++;
}
return bits;
}


int second_minima(int a[], unsigned int n) {


// build a tree of size of log2n in the form of 2d array
// 1st row represents all elements which fights for min
// candidate pairwise. winner of each pair moves to 2nd
// row and so on
int log_2n = log_2(n);
long comparison_count = 0;
// pair of ints : first element stores value and second
//                stores index of its first row
ii **p = new ii*[log_2n];
int i, j, k;
for (i = 0, j = n; i < log_2n; i++) {
p[i] = new ii[j];
j = j&1 ? j/2+1 : j/2;
}
for (i = 0; i < n; i++)
p[0][i] = make_pair(a[i], i);






// find minima using pair wise fighting
for (i = 1, j = n; i < log_2n; i++) {
// for each pair
for (k = 0; k+1 < j; k += 2) {
// find its winner
if (++comparison_count && p[i-1][k].first < p[i-1][k+1].first) {
p[i][k/2].first = p[i-1][k].first;
p[i][k/2].second = p[i-1][k].second;
}
else {
p[i][k/2].first = p[i-1][k+1].first;
p[i][k/2].second = p[i-1][k+1].second;
}


}
// if no. of elements in row is odd the last element
// directly moves to next round (row)
if (j&1) {
p[i][j/2].first = p[i-1][j-1].first;
p[i][j/2].second = p[i-1][j-1].second;
}
j = j&1 ? j/2+1 : j/2;
}






int minima, second_minima;
int index;
minima = p[log_2n-1][0].first;
// initialize second minima by its final (last 2nd row)
// potential candidate with which its final took place
second_minima = minima == p[log_2n-2][0].first ? p[log_2n-2][1].first : p[log_2n-2][0].first;
// minima original index
index = p[log_2n-1][0].second;
for (i = 0, j = n; i <= log_2n - 3; i++) {
// if its last candidate in any round then there is
// no potential candidate
if (j&1 && index == j-1) {
index /= 2;
j = j/2+1;
continue;
}
// if minima index is odd, then it fighted with its index - 1
// else its index + 1
// this is a potential candidate for second minima, so check it
if (index&1) {
if (++comparison_count && second_minima > p[i][index-1].first)
second_minima = p[i][index-1].first;
}
else {
if (++comparison_count && second_minima > p[i][index+1].first)
second_minima = p[i][index+1].first;
}
index/=2;
j = j&1 ? j/2+1 : j/2;
}




printf("-------------------------------------------------------------------------------\n");
printf("Minimum          : %d\n", minima);
printf("Second Minimum   : %d\n", second_minima);
printf("comparison count : %ld\n", comparison_count);
printf("Least No. Of Comparisons (");
printf("n+ceil(log2_n)-2) : %d\n", (int)(n+ceil(log(n)/log(2))-2));
return 0;
}


int main()
{
unsigned int n;
scanf("%u", &n);
int a[n];
int i;
for (i = 0; i < n; i++)
scanf("%d", &a[i]);
second_minima(a,n);
return 0;
}

function findSecondLargeNumber(arr){


var fLargeNum = 0;
var sLargeNum = 0;


for(var i=0; i<arr.length; i++){
if(fLargeNum < arr[i]){
sLargeNum = fLargeNum;
fLargeNum = arr[i];
}else if(sLargeNum < arr[i]){
sLargeNum = arr[i];
}
}


return sLargeNum;


}
var myArray = [799, -85, 8, -1, 6, 4, 3, -2, -15, 0, 207, 75, 785, 122, 17];

档号: http://www.ajaybadgujar.com/finding-second-largest-number-from-array-in-javascript/

具有 O (1)时间复杂性的一个好方法是使用最大堆。打两次电话，你就知道答案了。

假设提供的数组是 inPutArray = [1,2,5,8,7,3]预期的 O/P-> 7(第二大)

 take temp array
temp = [0,0], int dummmy=0;
for (no in inPutArray) {
if(temp[1]<no)
temp[1] = no
if(temp[0]<temp[1]){
dummmy = temp[0]
temp[0] = temp[1]
temp[1] = temp
}
}


print("Second largest no is %d",temp[1])

Gumbo 算法的 PHP 版本: http://sandbox.onlinephpfunctions.com/code/51e1b05dac2e648fd13e0b60f44a2abe1e4a8689

$numbers = [10, 9, 2, 3, 4, 5, 6, 7];


$largest = $numbers[0];
$secondLargest = null;
for ($i=1; $i < count($numbers); $i++) {
$number = $numbers[$i];
if ($number > $largest) {
$secondLargest = $largest;
$largest = $number;
} else if ($number > $secondLargest) {
$secondLargest = $number;
}
}


echo "largest=$largest, secondLargest=$secondLargest";

    int[] int_array = {4, 6, 2, 9, 1, 7, 4, 2, 9, 0, 3, 6, 1, 6, 8};
int largst=int_array[0];
int second=int_array[0];
for (int i=0; i<int_array.length; i++){
if(int_array[i]>largst) {
second=largst;
largst=int_array[i];
}
else if(int_array[i]>second  &&  int_array[i]<largst) {
second=int_array[i];
}
}

package com.array.orderstatistics;


import java.util.Arrays;
import java.util.Collections;


public class SecondLargestElement {


/**
*  Total Time Complexity will be n log n + O(1)
* @param str
*/
public static void main(String str[]) {
Integer[] integerArr = new Integer[] { 5, 1, 2, 6, 4 };






// Step1 : Time Complexity will be n log(n)
Arrays.sort(integerArr, Collections.reverseOrder());


// Step2 : Array.get Second largestElement
int secondLargestElement = integerArr[1];


System.out.println(secondLargestElement);
}
}

我想，按照上面的“最优算法使用 n + log n-2比较”，我想到的不使用二叉树来存储值的代码如下:

在每次递归调用期间，数组大小减半。

所以比较的次数是:

第一次迭代: n/2比较

第二次迭代: n/4比较

第三次迭代: n/8比较

直到 log n 迭代？

因此，total = > n-1比较？

function findSecondLargestInArray(array) {
let winner = [];
if (array.length === 2) {
if (array[0] < array[1]) {
return array[0];
} else {
return array[1];
}
}
for (let i = 1; i <= Math.floor(array.length / 2); i++) {
if (array[2 * i - 1] > array[2 * i - 2]) {
winner.push(array[2 * i - 1]);
} else {
winner.push(array[2 * i - 2]);
}
}
return findSecondLargestInArray(winner);
}

假设数组包含2 ^ n 个数字。

如果有6个数字，那么3个数字将移动到下一个级别，这是不正确的。

需要像8个数字 = > 4个数字 = > 2个数字 = > 1个数字 = > 2 ^ n 个数字