Найти 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;

использовать пузырьковую сортировку или алгоритм сортировки, который сортирует массив в порядке убывания. Не отсортировать массив. Всего два прохода. Первый проход дает самый большой элемент, а второй проход даст вам второй по величине элемент.

нет. сравнения для первого прохода: n-1

нет. сравнения для первого прохода: n-2

всего нет. сравнения для нахождения второго по величине: 2n-3

может быть, вы можете обобщить этот алгоритм. Если вам нужно 3-й по величине, то вы делаете 3 прохода.

по вышеуказанной стратегии вам не нужны никакие временные переменные, так как сортировка пузырьков и сортировка выбора сортировка на месте алгоритмов.

вот некоторый код, который может быть не оптимальным, но по крайней мере фактически находит 2-й по величине элемент:

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

требуется не менее N-1 сравнений, если самые большие 2 элемента находятся в начале массива и не более 2N-3 в худшем случае (один из первых 2 элементов является самым маленьким в массиве).

случае 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];  
      }  
}

извините, 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 сравнения и только проходит через список один раз.

Я знаю, что это старый вопрос, но вот моя попытка решить его, используя алгоритм турнира. Это похоже на решение , используемое @sdcvvc, но я использую двумерный массив для хранения элементов.

чтобы заставить вещи работать, есть два предположения:
1) количество элементов в массиве-это мощность 2
2) в массиве нет дубликатов

весь процесс состоит из двух шагов:
1. построение 2D массива с помощью сравнение двух по двум элементам. Первая строка в 2D массиве будет весь входной массив. Следующая строка содержит результаты сравнения предыдущей строки. Мы продолжаем сравнения на вновь построенном массиве и продолжаем строить 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;
    }

предположим, что предоставленный массив 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])

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

предполагая, что пространство не имеет значения,это самое маленькое, что я мог бы получить. Это требует 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]

попробуйте это.

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

использование сортировки подсчетом, а затем найти второй по величине элемент, начиная с индекса 0 к концу. Должно быть не менее 1 сравнения, не более n-1 (когда есть только один элемент!).

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

принятое решение по sdcvvc в 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;
}

Я просмотрел все сообщения выше, но я убежден, что реализация алгоритма турнира является лучшим подходом. Рассмотрим следующий алгоритм, опубликованный @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 = высота дерева

Так, нет. для сравнения найти минимум, используя турнирное дерево N-1 а для второго минимума-лог 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];

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

хорошим способом с O (1) временной сложностью было бы использовать max-heap. Позвоните в heapify дважды, и у вас есть ответ.

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

отсортируйте массив в порядке возрастания, затем назначьте переменную (n-1) - му члену.

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