Функция для поиска наибольшего и второго наибольшего элемента вектора

@GraK · Регистрация: 22.01.2017

Студворк — интернет-сервис помощи студентам

Есть вектор который заполняется рандомно. И нужно найти два элемента - самое большое значение и второе по величине. И главным условием сделать это с линейной сложностью.

@_Ivana · 17.05.2017, 16:09

Так хоть 22 пробежки по контейнеру - это все равно линейная сложность

@GraK · 17.05.2017, 20:10 **[ТС]**

пробовал сделать так

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#define MIN -1
 
void sum_distnace(const std::vector<int>& arr,int size_v)
{
    
    int max=arr[0],second_max=MIN ;
    for(int i=0;i<size_v;i++)
    {
        if(arr[i]>max)
        {
            second_max=max;
            max=arr[i];
            
        }
            
    }
}

но ошибка при поиске второго максимума.
пример {16, 5,6,9,7,19,12,17,5}
max=19
second_max = 16
он не ищет дальше макс. эта функция подходит для отсортированного массива, а без сортировки нельзя?

@_Ivana · 17.05.2017, 21:14

Ну, сортировку в линейную сложность не уместишь, теоретический минимум n*log(n). Да и с сортировкой любой дурак решит. Значит, можно без сортировки

oldnewyear · 18.05.2017, 00:49

Используйте алгоритм Quickselect

Добавлено через 4 минуты
Хотя, зачем..

@sourcerer · 18.05.2017, 08:15

GraK, всё уже придумано до нас - алгоритм std::max_element. Сложность линейная.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <algorithm>
#include <random>
#include <ctime>
 
using Item = int;
 
int main()
{
    const int ARR_SIZE = 12;
 
    std::vector <Item> ivec(ARR_SIZE);
 
    Item first = 10;
    Item last = 99;
 
    auto random_number_generator =
        [&first, &last]() -> decltype(first)
        {
            static std::mt19937 generator(time(0));
            std::uniform_real_distribution<> distribution(first, last);
            return distribution(generator) ;
        };
 
    std::generate(ivec.begin(), ivec.end(), random_number_generator);
 
    for (const auto & elem : ivec)
        std::cout << elem << ' ';
 
    auto iterToFirstMaxElem = std::max_element(ivec.begin(), ivec.end());
    auto iterToSecondMaxElem = std::max_element(iterToFirstMaxElem + 1, ivec.end());
 
    std::cout
        << "\nFirst maximal element is " << *iterToFirstMaxElem
        << "\nSecond maximal element is " << *iterToSecondMaxElem;
}

Добавлено через 12 минут
GraK, я поторопился. Надо ещё код поправить, иногда неправильно считает.

Добавлено через 3 минуты
GraK, вот исправленный вариант:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <algorithm>
#include <random>
#include <ctime>
 
using Item = int;
 
int main()
{
    const int ARR_SIZE = 12;
 
    std::vector <Item> ivec(ARR_SIZE);
 
    Item firstValue = 10;
    Item lastValue = 99;
 
    auto random_number_generator =
        [firstValue, lastValue]() -> decltype(firstValue)
        {
            static std::mt19937 generator(time(0));
            std::uniform_real_distribution<> distribution(firstValue, lastValue);
            return distribution(generator) ;
        };
 
    std::generate(ivec.begin(), ivec.end(), random_number_generator);
 
    for (const auto & elem : ivec)
        std::cout << elem << ' ';
 
    auto iterToFirstMaxElem = std::max_element(ivec.begin(), ivec.end());
    decltype(iterToFirstMaxElem) iterToSecondMaxElem;
 
    if (iterToFirstMaxElem + 1 < ivec.end())
        iterToSecondMaxElem = std::max_element(iterToFirstMaxElem + 1, ivec.end());
    else
        iterToSecondMaxElem = std::max_element(ivec.begin(), iterToFirstMaxElem);
 
    std::cout
        << "\nFirst maximal element is " << *iterToFirstMaxElem
        << "\nSecond maximal element is " << *iterToSecondMaxElem;
}

Добавлено через 15 минут
GraK, всё равно иногда неправильно считает. Надо ещё подумать.

@Manowar · 18.05.2017, 08:28

gru74ik, у Вас находит второй максимальный после первого максимального,

а нужно, как я понял, просто второй элемент.

@Manowar · 18.05.2017, 08:30

Функция для поиска наибольшего и второго наибольшего элемента вектора

@sourcerer · 18.05.2017, 08:43

GraK, мановар, в общем, проще отсортировать вектор и вывести два последних значения:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <algorithm>
#include <random>
#include <ctime>
 
using Item = int;
 
int main()
{
    const int ARR_SIZE = 12;
 
    std::vector <Item> ivec(ARR_SIZE);
 
    Item firstValue = 10;
    Item lastValue = 99;
 
    auto random_number_generator =
        [firstValue, lastValue]() -> decltype(firstValue)
        {
            static std::mt19937 generator( time( 0 ) );
            std::uniform_real_distribution<> distribution( firstValue, lastValue );
            return distribution( generator ) ;
        };
 
    std::generate(ivec.begin(), ivec.end(), random_number_generator);
 
    for (const auto & elem : ivec)
        std::cout << elem << ' ';
 
    std::sort(ivec.begin(), ivec.end());
 
    std::cout
        << "\nFirst maximal element is " << *(ivec.end() - 1)
        << "\nSecond maximal element is " << *(ivec.end() - 2);
}

@Manowar · 18.05.2017, 08:47

gru74ik, сложность уже не линейная, не подходит к заданию.
Опять же Вы берете последние 2 элемента, а если у нас максимальных выпало 2 или 3. Второй по значению окажется опять максимальным.

@sourcerer · 18.05.2017, 09:29

мановар, а если в std::set закинуть наш вектор?

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <algorithm>
#include <random>
#include <ctime>
#include <set>
 
using Item = int;
 
int main()
{
    const int ARR_SIZE = 12;
 
    std::vector <Item> iVec(ARR_SIZE);
 
    Item firstValue = 10;
    Item lastValue = 99;
 
    auto random_number_generator =
        [firstValue, lastValue]() -> decltype(firstValue)
        {
            static std::mt19937 generator( time( 0 ) );
            std::uniform_real_distribution<> distribution( firstValue, lastValue );
            return distribution( generator ) ;
        };
 
    std::generate(iVec.begin(), iVec.end(), random_number_generator);
 
    for (const auto & elem : iVec)
        std::cout << elem << ' ';
    std::cout << "\n\n";
 
    std::set<Item> mySet(iVec.begin(), iVec.end());
 
    auto it = mySet.end();
    std::cout << "\nFirst maximal element is " << *(--it);
    std::cout << "\nSecond maximal element is " << *(--it);
}

Добавлено через 2 минуты
Как бы ещё узнать, за какое время это всё выполняется?

Добавлено через 3 минуты

Сообщение от GraK

сделать это с линейной сложностью

GraK, линейной или меньше? Или именно с линейной? То есть, если за время, меньше, чем линейное выполняется, то уже не годится?

@sourcerer · 18.05.2017, 09:35

мановар, мда, тоже не подойдёт. Сложность создания сета из несортированного вектора больше, чем линейная:

@Manowar · 18.05.2017, 09:54

gru74ik, а чем max_element не подходит?

Добавлено через 2 минуты

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include "stdafx.h"
#include <iostream>
#include <vector>
#include <algorithm>
 
int main()
{
    int n = 0;
    std::vector <int> v{ 99, 99, 99, 45, 99, 5, 10, 44, 22, 99, 34, 12 };
 
    auto fist_max = *max_element(v.begin(), v.end());
 
    std::cout << "Max. element 1 = " << fist_max << std::endl;
 
    if (fist_max == v[0])
    {
        n = 1;
        while (fist_max == v[n])
            n++;
    }   
     auto second_max = *max_element(v.begin() + n, v.end(), [&fist_max](const int &x, const int &y) { return  x < y && y != fist_max; });
 
    std::cout << "Max. element 2 = " << second_max << std::endl;
 
    system("pause");
}

MrGluck · 18.05.2017, 09:56

Сообщение от _Ivana

Так хоть 22 пробежки по контейнеру - это все равно линейная сложность

А если размер контейнера равен 22?)

@sourcerer · 18.05.2017, 10:02

мановар, как минимум тем, что алгоритм std::max_element вызывается дважды. Значит сложность будет O(2n), разве нет? Или это не так считается?

Плюс ещё цикл там у тебя. Это точно у тебя линейная сложность?

MrGluck · 18.05.2017, 10:13

Сообщение от gru74ik

вызывается дважды. Значит сложность будет O(2n), разве нет?

2N всё равно линейная, константные коэффициенты отбрасываются

@Manowar · 18.05.2017, 10:14

Сообщение от gru74ik

Значит сложность будет O(2n), разве нет? Или это не так считается?

gru74ik, не знаю (я самообучающийся, до сложностей алгоритмов еще не добрался), думал Вы подскажите.

Сообщение от gru74ik

Плюс ещё цикл там у тебя. Это точно у тебя линейная сложность?

Да вроде ничего навороченного, идем по порядку. Хотя ведь в самом алгоритме max_element заложены циклы и сравнения.

MrGluck · 18.05.2017, 10:19

мановар, если что асимптотическая сложность можно глянуть тут, в конце описания алгоритма/метода контейнера
Например, для max_element

Complexity
Linear in one less than the number of elements compared.

@Manowar · 18.05.2017, 10:28

MrGluck, да глянул и там и тут http://ru.cppreference.com/w/c... ax_element
Эти два сайта одни из основных. Такими темпами и по англикски скоро свободно переводить начну.

@sourcerer · 18.05.2017, 11:44

Сообщение от MrGluck

2N всё равно линейная, константные коэффициенты отбрасываются

Ну, если так, то можно и вот так тогда:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <iostream>
#include <algorithm>
#include <random>
#include <ctime>
 
using Item = int;
 
int main()
{
    const int ARR_SIZE = 12;
 
    std::vector <Item> ivec(ARR_SIZE);
 
    Item firstValue = 10;
    Item lastValue = 99;
 
    auto random_number_generator =
        [firstValue, lastValue]() -> decltype(firstValue)
        {
            static std::mt19937 generator(time(0));
            std::uniform_real_distribution<> distribution(firstValue, lastValue);
            return distribution(generator) ;
        };
 
    std::generate(ivec.begin(), ivec.end(), random_number_generator);
 
    for (const auto & elem : ivec)
        std::cout << elem << ' ';
 
    auto iterToFirstMaxElem = std::max_element(ivec.begin(), ivec.end());
    decltype(iterToFirstMaxElem) iterToSecondMaxElem;
 
    if (iterToFirstMaxElem + 1 == ivec.end())
    {
        iterToSecondMaxElem =
            std::max_element
                (
                    ivec.begin(),
                    iterToFirstMaxElem,
                    [iterToFirstMaxElem](const int &x, const int &y)
                    {  // лямбда-выражение честно стырено у коллеги под ником "мановар"
                        return  x < y && y != *iterToFirstMaxElem;
                    }
                );
    }
    else if (iterToFirstMaxElem == ivec.begin())
    {
        iterToSecondMaxElem =
            std::max_element
                (
                    ivec.begin() + 1,
                    ivec.end(),
                    [iterToFirstMaxElem](const int &x, const int &y)
                    {
                        return  x < y && y != *iterToFirstMaxElem;
                    }
                );
    }
    else
    {
        auto iterToSecondMaxElemBeforeFirstMaxElem =
            std::max_element
                (
                    ivec.begin(),
                    iterToFirstMaxElem,
                    [iterToFirstMaxElem](const int &x, const int &y)
                    {
                        return  x < y && y != *iterToFirstMaxElem;
                    }
                );
        auto iterToSecondMaxElemAfterFirstMaxElem =
            std::max_element
                (
                    iterToFirstMaxElem + 1,
                    ivec.end(),
                    [iterToFirstMaxElem](const int &x, const int &y)
                    {
                        return  x < y && y != *iterToFirstMaxElem;
                    }
                );
        iterToSecondMaxElem =
            *iterToSecondMaxElemBeforeFirstMaxElem >= *iterToSecondMaxElemAfterFirstMaxElem
            ? iterToSecondMaxElemBeforeFirstMaxElem : iterToSecondMaxElemAfterFirstMaxElem;
    }
 
    std::cout
        << "\nFirst maximal element is " << *iterToFirstMaxElem
        << "\nSecond maximal element is " << *iterToSecondMaxElem;
}

Добавлено через 3 минуты
Предполагается, что вектор не состоит полностью из одинаковых элементов, не пуст, и не содержит только один элемент. Иначе нужно вставить соответствующие проверки.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .

Функция для поиска наибольшего и второго наибольшего элемента вектора

Решение

Решение

@GraK 0 / 0 / 0 Регистрация: 22.01.2017 Сообщений: 34

	Функция для поиска наибольшего и второго наибольшего элемента вектора 17.05.2017, 16:01. Показов 7569. Ответов 58 Метки нет (Все метки) Есть вектор который заполняется рандомно. И нужно найти два элемента - самое большое значение и второе по величине. И главным условием сделать это с линейной сложностью. 0

@_Ivana 4949 / 2289 / 287 Регистрация: 01.03.2013 Сообщений: 5,990 Записей в блоге: 32
	17.05.2017, 16:09
	Так хоть 22 пробежки по контейнеру - это все равно линейная сложность 0

@_Ivana 4949 / 2289 / 287 Регистрация: 01.03.2013 Сообщений: 5,990 Записей в блоге: 32
	17.05.2017, 21:14
	Ну, сортировку в линейную сложность не уместишь, теоретический минимум n*log(n). Да и с сортировкой любой дурак решит. Значит, можно без сортировки 0

oldnewyear 440 / 432 / 159 Регистрация: 21.05.2016 Сообщений: 1,338
	18.05.2017, 00:49
	Используйте алгоритм Quickselect Добавлено через 4 минуты Хотя, зачем.. 0

@Manowar 1719 / 568 / 187 Регистрация: 12.03.2016 Сообщений: 2,169
	18.05.2017, 08:28
	gru74ik, у Вас находит второй максимальный после первого максимального, а нужно, как я понял, просто второй элемент. 0

@Manowar 1719 / 568 / 187 Регистрация: 12.03.2016 Сообщений: 2,169
	18.05.2017, 08:30
	0

@Manowar 1719 / 568 / 187 Регистрация: 12.03.2016 Сообщений: 2,169
	18.05.2017, 08:47
	gru74ik, сложность уже не линейная, не подходит к заданию. Опять же Вы берете последние 2 элемента, а если у нас максимальных выпало 2 или 3. Второй по значению окажется опять максимальным. 0

@sourcerer Модератор 5288 / 2376 / 342 Регистрация: 20.02.2013 Сообщений: 5,773 Записей в блоге: 20
	18.05.2017, 09:35
	мановар, мда, тоже не подойдёт. Сложность создания сета из несортированного вектора больше, чем линейная: Миниатюры 0

@sourcerer Модератор 5288 / 2376 / 342 Регистрация: 20.02.2013 Сообщений: 5,773 Записей в блоге: 20
	18.05.2017, 10:02
	мановар, как минимум тем, что алгоритм std::max_element вызывается дважды. Значит сложность будет O(2n), разве нет? Или это не так считается? Плюс ещё цикл там у тебя. Это точно у тебя линейная сложность? 0

@Manowar 1719 / 568 / 187 Регистрация: 12.03.2016 Сообщений: 2,169
	18.05.2017, 10:28
	MrGluck, да глянул и там и тут http://ru.cppreference.com/w/c... ax_element Эти два сайта одни из основных. Такими темпами и по англикски скоро свободно переводить начну. 0