Подтвердить что ты не робот

Как мы можем найти второй максимум из массива эффективно?

Можно ли найти второе максимальное число из массива целых чисел, пройдя массив только один раз?

В качестве примера у меня есть массив из пяти целых чисел, из которых я хочу найти второе максимальное число. Вот попытка, которую я дал в интервью:

#define MIN -1
int main()
{
    int max=MIN,second_max=MIN;
    int arr[6]={0,1,2,3,4,5};
    for(int i=0;i<5;i++){
        cout<<"::"<<arr[i];
    }
    for(int i=0;i<5;i++){
        if(arr[i]>max){
            second_max=max;
            max=arr[i];          
        }
    }
    cout<<endl<<"Second Max:"<<second_max;
    int i;
    cin>>i;
    return 0;
}

Интервьюер, однако, придумал тестовый пример int arr[6]={5,4,3,2,1,0};, который предотвращает его переход в состояние if во второй раз. Я сказал интервьюеру, что единственный способ - разобрать массив два раза (два цикла for). У кого-нибудь есть лучшее решение?

4b9b3361

ОТВЕТЫ

Ответ 1

Инициализация max и second_max до -1 неверна. Что делать, если массив имеет значения, такие как {-2,-3,-4}?

Вместо этого вы должны взять первые 2 элемента массива (предположим, что массив имеет не менее 2 элементов), сравнить их, назначить меньший second_max, а более крупный - max:

if(arr[0] > arr[1]) {
 second_max = arr[1];
 max = arr[0];
} else {
 second_max = arr[0];
 max = arr[1];
}

Затем начните сравнение с третьим элементом и обновите max и/или second_max по мере необходимости:

for(int i = 2; i < arr_len; i++){
    // use >= n not just > as max and second_max can hav same value. Ex:{1,2,3,3}   
    if(arr[i] >= max){  
        second_max=max;
        max=arr[i];          
    }
    else if(arr[i] > second_max){
        second_max=arr[i];
    }
}

Ответ 2

Самое простое решение - использовать std::nth_element.

Ответ 3

Вам потребуется второе испытание:

 for(int i=0;i<5;i++){  
   if(arr[i]>max){  
     second_max=max;  
     max=arr[i];            
   }
   else if (arr[i] > second_max && arr[i] != max){
     second_max = arr[i];
   }
 }

Ответ 4

Здесь вы находитесь:

std::pair<int, int> GetTwoBiggestNumbers(const std::vector<int>& array)
{
    std::pair<int, int> biggest;
    biggest.first = std::max(array[0], array[1]);  // Biggest of the first two.
    biggest.second = std::min(array[0], array[1]); // Smallest of the first two.

    // Continue with the third.
    for(std::vector<int>::const_iterator it = array.begin() + 2;
        it != array.end();
        ++it)
    {
        if(*it > biggest.first)
        {
            biggest.second = biggest.first;
            biggest.first = *it;
        }
        else if(*it > biggest.second)
        {
            biggest.second = *it;
        }
    }

    return biggest;
}

Ответ 5

Ваш исходный код в порядке, вам просто нужно инициализировать переменные max и second_max. Используйте первые два элемента в массиве.

Ответ 6

Quickselect - это способ пойти с этим. Псевдокод доступен по этой ссылке, поэтому я просто объясню общий алгоритм:

QuickSelect for kth largest number:
    Select a pivot element
    Split array around pivot
    If (k < new pivot index)
       perform quickselect on left hand sub array
     else if (k > new pivot index)
       perform quickselect on right hand sub array (make sure to offset k by size of lefthand array + 1)
     else
       return pivot

Это, очевидно, основано на хорошем старом алгоритме быстрой сортировки.

Следуя этому алгоритму, всегда каждый раз выбираем нулевой элемент в качестве поворота:

select 4th largest number:
1) array = {1, 3, 2, 7, 11, 0, -4}
partition with 1 as pivot
{0, -4, _1_, 3, 2, 7, 11}
4 > 2 (new pivot index) so...

2) Select 1st (4 - 3) largest number from right sub array
array = {3, 2, 7, 11}
partition with 3 as pivot
{2, _3_, 7, 11}
1 < 2 (new pivot index) so...

3) select 1st largest number from left sub array
array = {2}

4) Done, 4th largest number is 2

После этого ваш массив будет в порядке undefined, это зависит от вас, если это проблема.

Ответ 7

Шаг 1. Решите первые два числа.
Шаг 2. Прокрутите оставшиеся числа. Шаг 3. Поддерживайте максимальный максимум и второй максимум. Шаг 4. При обновлении второго максимума помните, что вы не делаете максимальный и второй максимальный равным.

Протестировано для отсортированного ввода (восходящего и нисходящего), случайного ввода, ввода с дубликатами, отлично работает.

#include <iostream>
#define MAX 50
int GetSecondMaximum(int* data, unsigned int size)
{
    int max, secmax;
    // Decide on first two numbers
    if (data[0] > data[1])
    {
        max = data[0];
        secmax = data[1];
    }
    else
    {
        secmax = data[0];
        max = data[1];
    }
    // Loop through remaining numbers
    for (unsigned int i = 2; i < size; ++i)
    {
        if (data[i] > max)
        {
            secmax = max;
            max = data[i];
        }
        else if (data[i] > secmax && data[i] != max/*removes duplicate problem*/)
            secmax = data[i];
    }
    return secmax;
}
int main()
{
    int data[MAX];
    // Fill with random integers
    for (unsigned int i = 0; i < MAX; ++i)
    {
        data[i] = rand() % MAX;
        std::cout << "[" << data[i] << "] "; // Display input
    }
    std::cout << std::endl << std::endl;
    // Find second maximum
    int nSecondMax = GetSecondMaximum(data, MAX);
    // Display output
    std::cout << "Second Maximum = " << nSecondMax << std::endl;
    // Wait for user input
    std::cin.get();
    return 0;
}

Ответ 8

Другим способом решения этой проблемы является использование сравнений между элементами. Например,

a[10] = {1,2,3,4,5,6,7,8,9,10}

Сравните 1,2 и скажем max = 2 и second max = 1

Теперь сравните 3 и 4 и сравните наибольшее из них с макс.

if element > max
     second max = max
     element = max
else if element > second max
     second max = element

Преимущество этого заключается в том, что вы удаляете два числа всего за два сравнения.

Сообщите мне, если у вас возникли проблемы с пониманием этого.

Ответ 9

Проверьте это решение.

max1 = a[0];
max2 = a[1];

for (i = 1; i < n; i++)
{
    if (max1 < a[i])
    {
        max2 = max1;
        max1 = a[i];
    }

    if (max2 == max1) max2 = a[i + 1];

    if (max2 == a[n])
    {
        printf("All numbers are the same no second max.\n");
        return 0;
    }

    if (max2 < a[i] && max1 != a[i]) max2 = a[i];
}

Ответ 10

Вот что может сработать,

public static int secondLargest(int[] a){
    int max=0;
    int secondMax=0;

    for(int i=0;i<a.length;i++){
        if(a[i]<max){
            if(a[i]>secondMax){
                secondMax=a[i];
            }
            continue;
        }

        if(a[i]>max){
            secondMax=max;
            max=a[i];
        }

    }
    return secondMax;
}

Ответ 11

Верхняя граница должна быть n + log2⁡n-2, но она больше, чем O (n) в случае алгоритма случайного выбора, но в худшем случае она намного меньше. Решение может быть

  • построить дерево, как найти элемент MAX с n-1 сравнениями

    макс (N)  /\ max (N/2) max (N/2)

  • удалить MAX и снова найти MAX log2n - 1 сравнение

PS. Он использует дополнительную память, но быстрее, чем алгоритм случайного выбора, в худшем случае.

Ответ 12

Разве мы не можем отсортировать это в порядке убывания и взять 2-й элемент из отсортированного массива?

Ответ 13

Как насчет следующего ниже. make_heap - это O (n), поэтому это эффективно, и это 1 проход Мы находим второй макс, пользуясь тем преимуществом, что он должен быть одним из кучи родителя, у которого был максимум.

#include <algorithm>
#include <iostream>

int main()
{
    int arr[6]={0,1,2,3,4,5};

    std::make_heap(arr, arr+6);
    std::cout << "First Max: " << arr[0] << '\n';
    std::cout << "Second Max: " << std::max(arr[1], arr[2]) << '\n';
    return 0;
}

Ответ 14

int max,secondMax;
max=secondMax=array[0];
                                                for(int i=0;i<array.length;i++)
    {                                                   if(array[i]>max)                                                    {                                           max=array[i];                                                   }
                                                        if(array[i]>secondMax && array[i]<max)                                                  {
    secondMax=array[i];                                                 }
    }

Ответ 15

#include <iostream>
using namespace std;

int main() {

   int  max = 0;
    int sec_Max = 0;

    int array[] = {81,70,6,78,54,77,7,78};

    int loopcount = sizeof(array)/sizeof(int);

    for(int i = 0 ; i < loopcount ; ++i)
    {

        if(array[i]>max)
        {
            sec_Max = max;
            max = array[i];
        }

        if(array[i] > sec_Max && array[i] < max)
        {
            sec_Max = array[i];
        }
    }

    cout<<"Max:" << max << " Second Max: "<<sec_Max<<endl;

    return 0;
}

Ответ 16

// Set the first two different numbers as the maximum and second maximum numbers

 int max = array[0];
 int i = 1;
//n is the amount of numbers

 while (array[i] == max && i < n) i++;
 int sec_max = array[i];
 if( max < sec_max ) {
    tmp = sec_max;
    sec_max = max;
    max = tmp;
 }

//find the second maximum number

 for( ; i < n; ++i ) {
   if( array[i] > max ) {
     sec_max = max;
     max = array[i];
   } else if( array[i] > sec_max && array[i] != max ) {
     sec_max = array[i];
   }
 }
 printf("The second maximum number is %d\n", sec_max);