Как мы можем найти второй максимум из массива эффективно?
Можно ли найти второе максимальное число из массива целых чисел, пройдя массив только один раз?
В качестве примера у меня есть массив из пяти целых чисел, из которых я хочу найти второе максимальное число. Вот попытка, которую я дал в интервью:
#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). У кого-нибудь есть лучшее решение?
Ответы
Ответ 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 + log2n-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);
