用最less的比较次数查找数组中第二大元素

对于大小为N的数组，需要比较的数量是多less？

Answer 1

最佳algorithm使用n + log n-2比较。 把元素看作是竞争对手，而锦标赛将会把它们排在前面。

首先，比较树中的元素

  | / \ | | / \ / \ xxxx 

这需要n-1次比较，并且每个元素在最多n次比较中涉及比较。 你会发现赢家的最大元素。

第二大元素必定失去了与胜者的一场比赛（他不能失去一个不同的元素的比赛），所以他是赢家所面对的log n元素之一。 您可以使用log n – 1比较来find其中的哪一个。

通过对手论证certificate了最优性。 请参阅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或~chandra/documents/6363/lbd.pdf

Answer 2

您可以通过至多2·（ N -1）比较和两个variables保持最大值和第二大值find第二大值：

 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

使用按降序对数组进行sorting的Bubble sort或Selectionsortingalgorithm。 不要完全排列arrays。 只有两个通行证。 第一遍给出最大的元素，第二遍将给你第二大元素。

第一次通过的比较数：n-1第一次通过的比较次数：n-2总数 find第二大比较：2n-3

也许你可以推广这个algorithm。 如果你需要第三大，那么你做3次传球。

通过上述策略，您不需要任何临时variables，因为Bubble sort和Selectionsorting就地sortingalgorithm。

Answer 4

这里有一些代码可能不是最优的，但至less可以find第二大元素：

 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个元素在arrays的开始处，则至less需要N-1个比较，并且在最差的情况下最多2N-3个（前两个元素中的一个是arrays中最小的）。

Answer 5

案例1 – > 9 8 7 6 5 4 3 2 1
案例2 – > 50 10 8 25 ……..
案例3 – > 50 50 10 8 25 ………
案例4 – > 50 50 10 8 50 25 …….

 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]; } } 

Answer 6

对不起，JS代码…

testing了两个input：

 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比较，只能通过列表一次。

Answer 7

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

为了使事情有效，有两个假设：
1）数组中元素的个数是2的幂
2）数组中没有重复项

整个过程包括两个步骤：
1.通过比较两个两个元素来构build二维数组。 二维数组中的第一行是整个input数组。 下一行包含前一行的比较结果。 我们继续在新构build的数组上进行比较，并继续构build二维数组，直到只有一个元素（最大一个）的数组到达。
2.我们有一个2D数组，最后一行只包含一个元素：最大的一个。 我们继续从底部到顶部，在每个数组中find被最大“打”的元素，并将其与当前“第二大”值进行比较。 要find最大的元素，并避免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; } 

Answer 8

假设提供的数组是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]) 

Answer 9

假设空间是不相关的，这是我能得到的最小的空间。 在最坏的情况下需要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] 

Answer 10

尝试这个。

 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() 

Answer 11

使用计数sorting，然后find第二大元素，从索引0开始到结束。 应该至less有1个比较，最多n-1 （当只有一个元素！）。

Answer 12

 #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); } 

Answer 13

sdcvvc在C ++ 11中接受的解决scheme

 #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; } 

Answer 14

我已经完成了上面所有的post，但我相信比赛algorithm的实施是最好的方法。 让我们考虑由@Gumbo发布的以下algorithm

 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; 

这是非常好的情况下，我们要find一个数组中的第二大数字。 它有（2n-1）个比较。 但是，如果你想计算第三大的数字或第几个最大的数字。 上述algorithm不起作用。 你需要另一个程序。

所以，我相信比赛algorithm的方法是最好的，这是链接 。

Answer 15

以下解决scheme需要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 

Answer 16

它可以在n + ceil（log n） – 2比较中完成。

解决scheme：需要n-1次比较才能获得最小值。

但为了达到最低限度，我们将build立一个锦标赛，其中每个元素将被成对地分组。 像网球比赛和任何一轮的冠军都会前进。

这棵树的高度将被logging，因为我们每一轮都是一半。

获得第二个最低限度的想法是在前一轮中将被最低限度的候选人打败。 所以，我们需要在潜在的候选人中find最低限度（被最低限度打败）。

潜在的候选人将是日志n =树的高度

所以不行。 比较find最小使用锦标赛树是n-1和第二个最小值是log n -1总和up = 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; } 

Answer 17

 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/

Answer 18

O（1）时间复杂性的一个好方法是使用最大堆。 呼叫heapify两次，你有答案。

Answer 19

Gumboalgorithm的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"; 

Answer 20

  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]; } } 

Answer 21

 class solution: def SecondLargestNumber (self,l): Largest = 0 secondLargest = 0 for i in l: if i> Largest: secondLargest = Largest Largest = max(Largest, i) return Largest, secondLargest 

Answer 22

按升序对数组进行sorting，然后为（n-1）项赋一个variables。