Encuentra el segundo elemento más grande en una matriz con un número mínimo de comparaciones

Para una matriz de tamaño N, ¿cuál es el número de comparaciones necesarias?

El algoritmo óptimo usa n + log n-2 comparaciones. Piense en elementos como competidores, y un torneo los clasificará.

Primero, compare los elementos, como en el árbol

  | / \ | | / \ / \ xxxx 

esto toma n-1 comparaciones y cada elemento está involucrado en la comparación a lo sumo log n veces. Encontrarás el elemento más grande como el ganador.

El segundo elemento más grande debe haber perdido una coincidencia con el ganador (no puede perder un partido con un elemento diferente), por lo que es uno de los elementos de registro n contra el que el ganador ha jugado. Puede encontrar cuál de ellos usando log n – 1 comparaciones.

La optimalidad se prueba mediante el argumento del adversario. Consulte https://math.stackexchange.com/questions/1601 o http://compgeom.cs.uiuc.edu/~jeffe/teaching/497/02-selection.pdf o http: //www.imada.sdu. dk / ~ jbj / DM19 / lb06.pdf o https://www.utdallas.edu/~chandra/documents/6363/lbd.pdf

Puede encontrar el segundo valor más grande con, como máximo, 2 · ( N -1) comparaciones y dos variables que tienen el valor más grande y el segundo más grande:

 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; 

Utilice el algoritmo de ordenación de selección o selección de burbuja que ordena la matriz en orden descendente. No clasifique la matriz por completo. Solo dos pases. El primer pase da el elemento más grande y el segundo pase le dará el segundo elemento más grande.

Nº de comparaciones para el primer pase: n-1

Nº de comparaciones para el primer pase: n-2

Total no. de comparación para encontrar el segundo más grande: 2n-3

Puede ser que puedas generalizar este algoritmo. Si necesitas el tercero más grande, entonces haces 3 pases.

Con la estrategia anterior, no necesita ninguna variable temporal ya que los algoritmos de ordenación de burbuja y selección están en su lugar .

Aquí hay un código que podría no ser óptimo, pero que al menos en realidad encuentra el segundo elemento más grande:

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

Necesita al menos N-1 comparaciones si los 2 elementos más grandes se encuentran al comienzo de la matriz y, como máximo, 2N-3 en el peor de los casos (uno de los 2 primeros elementos es el más pequeño de la matriz).

caso 1 -> 9 8 7 6 5 4 3 2 1
caso 2 -> 50 10 8 25 ……..
caso 3 -> 50 50 10 8 25 ………
caso 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;imax1) { max2=max1; max1=a[i]; } else if(a[i]>max2 &&a[i]!=max1) max2=a[i]; else if(max1==max2) max2=a[i]; } } 

Lo siento, código JS …

Probado con las dos entradas:

 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 

Esto debería tener un máximo de a.length * 2 comparaciones y solo pasa por la lista una vez.

Sé que esta es una vieja pregunta, pero aquí está mi bash de resolverla, haciendo uso del algoritmo del torneo. Es similar a la solución utilizada por @sdcvvc, pero estoy usando una matriz bidimensional para almacenar elementos.

Para que las cosas funcionen, hay dos suposiciones:
1) número de elementos en la matriz es el poder de 2
2) no hay duplicados en la matriz

Todo el proceso consta de dos pasos:
1. construir una matriz 2D comparando dos por dos elementos. La primera fila en la matriz 2D será la matriz de entrada completa. La siguiente fila contiene los resultados de las comparaciones de la fila anterior. Continuamos las comparaciones en la matriz recién construida y seguimos construyendo la matriz 2D hasta que se alcanza una matriz de un solo elemento (la más grande).
2. tenemos una matriz 2D donde la última fila contiene solo un elemento: el más grande. Continuamos yendo de abajo hacia arriba, en cada matriz encontramos el elemento que fue “superado” por el más grande y lo comparamos con el valor actual “segundo más grande”. Para encontrar el elemento golpeado por el más grande, y para evitar las comparaciones O (n), debemos almacenar el índice del elemento más grande en la fila anterior. De esa forma podemos verificar fácilmente los elementos adyacentes. En cualquier nivel (arriba del nivel raíz), los elementos adyacentes se obtienen como:

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

donde rootIndex es el índice del elemento más grande (raíz) en el nivel anterior.

Sé que la pregunta pide C ++, pero aquí está mi bash de resolverlo en Java. (He usado listas en lugar de matrices, para evitar un cambio complicado del tamaño de la matriz y / o cálculos de tamaño de matriz innecesarios)

 public static Integer findSecondLargest(List list) { if (list == null) { return null; } if (list.size() == 1) { return list.get(0); } List> structure = buildUpStructure(list); System.out.println(structure); return secondLargest(structure); } public static List> buildUpStructure(List list) { List> newList = new ArrayList>(); List tmpList = new ArrayList(list); newList.add(tmpList); int n = list.size(); while (n>1) { tmpList = new ArrayList(); for (int i = 0; i> structure) { int n = structure.size(); int rootIndex = 0; Integer largest = structure.get(n-1).get(rootIndex); List 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; } 

Supongamos que el conjunto provisto es inPutArray = [1,2,5,8,7,3] O / P esperado -> 7 (el segundo más grande)

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

Versión PHP del algoritmo Gumbo: 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"; 

Suponiendo que el espacio es irrelevante, este es el más pequeño que podría obtenerlo. Requiere 2 * n comparaciones en el peor de los casos, y n comparaciones en el mejor de los casos:

 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] 

prueba esto.

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

debería funcionar como un encanto. bajo en complejidad

aquí hay un código de 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() 

Utilice la clasificación por conteo y luego encuentre el segundo elemento más grande, comenzando desde el índice 0 hacia el final. Debe haber al menos 1 comparación, como máximo n-1 (cuando solo hay un elemento).

 #include 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 

La solución aceptada por sdcvvc en C ++ 11.

 #include  #include  #include  #include  #include  using std::vector; using std::cout; using std::endl; using std::random_shuffle; using std::min; using std::max; vector create_tournament(const vector& input) { // make sure we have at least two elements, so the problem is interesting if (input.size() <= 1) { return input; } vector 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& 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& v) { for (const auto& el : v) { cout << el << " "; } cout << endl; } int main() { vector 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; } 

He revisado todas las publicaciones anteriores, pero estoy convencido de que la implementación del algoritmo del Torneo es el mejor enfoque. Consideremos el siguiente algoritmo publicado por @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; 

Es muy bueno en caso de que encontremos el segundo número más grande en una matriz. Tiene (2n-1) número de comparaciones. Pero, ¿qué ocurre si desea calcular el tercer número más grande o algún número kth más grande? El algoritmo anterior no funciona. Tienes otro procedimiento.

Por lo tanto, creo que el enfoque de algoritmo de torneo es el mejor y aquí está el enlace para eso.

La siguiente solución tomaría 2 (N-1) comparaciones:

 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 

Se puede hacer en n + ceil (log n) – 2 comparación.

Solución: toma n-1 comparaciones para obtener un mínimo.

Pero para obtener un mínimo vamos a construir un torneo en el que cada elemento se agrupe en pares. como un torneo de tenis y el ganador de cualquier ronda seguirá adelante.

La altura de este árbol será la de inicio de sesión desde la mitad de cada ronda.

La idea de obtener el segundo mínimo es que será superado por un candidato mínimo en una ronda previa. Por lo tanto, necesitamos encontrar un mínimo de candidatos potenciales (vencidos por mínimo).

Los posibles candidatos serán log n = altura del árbol

Entonces, no. de comparación para encontrar el mínimo usando el árbol del torneo es n-1 y para el segundo mínimo es log n -1 sums arriba = n + ceil (log n) – 2

Aquí está el código C ++

 #include  #include  #include  #include  #include  using namespace std; typedef pair 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 

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

Una buena forma con O (1) complejidad de tiempo sería usar un máximo de montón. Llama a heapify dos veces y tienes la respuesta.

  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; ilargst) { second=largst; largst=int_array[i]; } else if(int_array[i]>second && int_array[i] 

Clasifique la matriz en orden ascendente y luego asigne una variable al término (n-1) th.

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