ti-enxame.com

Encontre o segundo maior elemento em uma matriz com um número mínimo de comparações

Para uma matriz de tamanho N, qual é o número de comparações necessárias?

63
nababa

O algoritmo ideal usa comparações n + log n-2. Pense em elementos como competidores e um torneio vai classificá-los.

Primeiro, compare os elementos, como na árvore

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

isso leva n-1 comparações e cada elemento está envolvido na comparação no máximo log n vezes. Você encontrará o maior elemento como vencedor.

O segundo maior elemento deve ter perdido um jogo para o vencedor (ele não pode perder uma partida para um elemento diferente), então ele é um dos elementos do log n que o vencedor jogou contra. Você pode encontrar qual deles usando as comparações log n - 1.

A otimalidade é comprovada via argumento adversário. Consulte https://math.stackexchange.com/questions/1601 ou http://compgeom.cs.uiuc.edu/~jeffe/teaching/497/02-selection.pdf ou http://www.imada.sdu.dk/~jbj/DM19/lb06.pdf ou https://www.utdallas.edu/~chandra/documents/6363/lbd.pdf

108
sdcvvc

Você pode encontrar o segundo maior valor com no máximo 2 · (N- 1) comparações e duas variáveis ​​que detêm o maior e o segundo maior valor:

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;
11
Gumbo

Use o algoritmo Bubble Sort ou Selection Sort, que classifica o array em ordem decrescente. Não classifique a matriz completamente. Apenas dois passes. Primeira passagem dá o maior elemento e a segunda passagem lhe dará o segundo maior elemento.

Nº de comparações para a primeira passagem: n-1

Nº de comparações para primeira passagem: n-2

Total não de comparação para encontrar o segundo maior: 2n-3

Pode ser que você possa generalizar esse algoritmo. Se você precisa do 3º maior, então você faz 3 passes.

Pela estratégia acima, você não precisa de nenhuma variável temporária, pois o tipo Bubble Sort e Selection sort são no local ordenação algoritmos.

9
Rohit Bansod

Aqui está algum código que pode não ser o ideal, mas pelo menos encontra o segundo maior elemento:

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

Ele precisa de pelo menos N-1 comparações se os maiores 2 elementos estiverem no início do array e no máximo 2N-3 no pior dos casos (um dos primeiros 2 elementos é o menor no array).

2
x4u

Versão PHP do 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";
1
forsberg

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;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];  
      }  
}
1
achal kumar

Suponha que array seja inPutArray = [1,2,5,8,7,3] esperado O/P -> 7 (segundo maior)

 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])
1
Kiran K

Eu sei que esta é uma questão antiga, mas aqui está minha tentativa de resolvê-lo, fazendo uso do Algoritmo de Torneio. É semelhante à solução usada pelo @sdcvvc, mas estou usando uma matriz bidimensional para armazenar elementos.

Para fazer as coisas funcionarem, existem duas suposições:
1) número de elementos na matriz é o poder de 2
2) não há duplicatas na matriz

Todo o processo consiste em duas etapas:
1. construção de um array 2D comparando dois por dois elementos. A primeira linha na matriz 2D será toda a matriz de entrada. A próxima linha contém os resultados das comparações da linha anterior. Continuamos as comparações no array recém-construído e continuamos construindo o array 2D até que uma matriz de apenas um elemento (o maior) seja atingida.
2. temos uma matriz 2D em que a última linha contém apenas um elemento: o maior. Continuamos indo de baixo para cima, em cada matriz encontrando o elemento que foi "espancado" pelo maior e comparando-o com o "segundo maior" valor atual. Para encontrar o elemento batido pelo maior, e para evitar comparações O(n), devemos armazenar o índice do maior elemento na linha anterior. Dessa forma, podemos facilmente verificar os elementos adjacentes. Em qualquer nível (acima do nível da raiz), os elementos adjacentes são obtidos como:

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

em que rootIndex é o índice do maior elemento (raiz) no nível anterior.

Eu sei que a pergunta pede por C++, mas aqui está minha tentativa de resolvê-lo em Java. (Eu usei listas em vez de matrizes, para evitar a mudança do tamanho da matriz e/ou cálculos desnecessários de tamanho de matriz)

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;
    }
1
Maggie

Desculpe, código JS ...

Testado com as duas 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

Isso deve ter um máximo de comparações de comprimento * 2 e só passa pela lista uma vez.

1
geekdenz

Uma boa maneira com a complexidade do tempo O(1) seria usar um heap máximo. Chame o heap duas vezes e você tem a resposta.

0
Harsh Gupta

tente isso.

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

deve funcionar como um encanto. baixa complexidade.

aqui está um código 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()
0
sabbibJAVA
#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);
}
0
prawin

Use a ordenação por contagem e depois encontre o segundo maior elemento, começando do índice 0 até o final. Deve haver pelo menos 1 comparação, no máximo n-1 (quando há apenas um elemento!). 

0
lyfzabrutalcode

A solução a seguir levaria 2(N-1) comparações:

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
0
user3214392

A solução aceita pelo sdcvvc em C++ 11.

#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;
}
0
Dimitris Leventeas

Isso pode ser feito na comparação n + ceil (log n) - 2.

Solução: São necessárias comparações n-1 para obter o mínimo.

Mas, para obter o mínimo, construiremos um torneio no qual cada elemento será agrupado em pares. como um torneio de tênis e vencedor de qualquer rodada seguirá em frente.

Altura desta árvore será log n desde que metade em cada rodada.

A ideia de obter o segundo mínimo é que ele será derrotado pelo candidato mínimo em uma das rodadas anteriores. Então, precisamos encontrar o mínimo em potenciais candidatos (vencidos pelo mínimo).

Candidatos potenciais serão log n = altura da árvore

Então não. de comparação para encontrar o mínimo usando a árvore do torneio é n-1 e para o segundo mínimo é log n -1 resume = n + ceil (log n) - 2

Aqui está o código 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;
}
0
prakharjain
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];

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

0
coder
    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];
        } 
    }
0
Usman

Eu passei por todos os posts acima, mas estou convencido de que a implementação do algoritmo de torneio é a melhor abordagem. Vamos considerar o seguinte algoritmo postado 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;

É muito bom no caso de encontrarmos o segundo maior número em uma matriz. Tem (2n-1) número de comparações. Mas e se você quiser calcular o terceiro maior número ou um k maior número. O algoritmo acima não funciona. Você chegou a outro procedimento. 

Então, acredito que a abordagem de algoritmo de torneio é a melhor e aqui está o link para isso.

0
Baradwaj Aryasomayajula

Eu suponho, siga o "algoritmo ideal usa n + log n-2 comparações" de cima, o código que eu vim com que não usa árvore binária para armazenar o valor seria o seguinte:

Durante cada chamada recursiva, o tamanho da matriz é cortado pela metade.

Então o número de comparação é: 

1ª iteração: n/2 comparações

2ª iteração: n/4 comparações

3ª iteração: n/8 comparações

... Até logar n iterações?

Portanto, total => n - 1 comparações?

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

Assumindo que a matriz contenha 2 ^ n número de números.

Se houver 6 números, então 3 números passarão para o próximo nível, o que não está certo.

Precisa de 8 números => 4 número => 2 número => 1 número => 2 ^ n número de número

0
Ou Ye

Assumindo que o espaço é irrelevante, este é o menor que eu poderia conseguir. Requer 2 * n comparações no pior caso, e n comparações no melhor caso:

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]
0
riwalk