Найти второй по величине элемент в массиве с минимальным количеством сравнений

Question

Какое количество требуемых сравнений для массива размера N?

Answer 1

    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 2

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

Answer 3

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 4

Это можно сделать в n + ceil (log n) - 2 сравнения.

Решение: для получения минимума требуется n-1 сравнений.

Но чтобы получить минимум, мы построимтурнир, в котором каждый элемент будет сгруппирован в пары.как теннисный турнир, и победитель любого раунда пойдет вперёд.

Высота этого дерева будет равна log n, так как мы наполовину в каждом раунде.

Идея получить второй минимум - этопобежден минимальным кандидатом в одном из предыдущих туров.Итак, нам нужно найти минимум у потенциальных кандидатов (побитый минимумом).

Потенциальными кандидатами будут log n = высота дерева

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

Answer 5

Следующее решение будет принимать 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 6

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

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

Answer 7

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

Answer 8

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

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

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