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

@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 минуты
Предполагается, что вектор не состоит полностью из одинаковых элементов, не пуст, и не содержит только один элемент. Иначе нужно вставить соответствующие проверки.

Новые блоги и статьи Все статьи Все блоги /
Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114	Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .	Модель микоризы: классовый агентный подход 2 anaschu 06.01.2026 репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .	Расчёт токов в цепи постоянного тока igorrr37 05.01.2026 / * Дана цепь постоянного тока с сопротивлениями и напряжениями. Надо найти токи в ветвях. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и решает её. Последовательность действий:. . .
Новый CodeBlocs. Версия 25.03 palva 04.01.2026 Оказывается, недавно вышла новая версия CodeBlocks за номером 25. 03. Когда-то давно я возился с только что вышедшей тогда версией 20. 03. С тех пор я давно снёс всё с компьютера и забыл. Теперь. . .	Модель микоризы: классовый агентный подход anaschu 02.01.2026 Раньше это было два гриба и бактерия. Теперь три гриба, растение. И на уровне агентов добавится между грибами или бактериями взаимодействий. До того я пробовал подход через многомерные массивы,. . .	Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .

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

Решение

Решение

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

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

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

@_Ivana 4949 / 2289 / 287 Регистрация: 01.03.2013 Сообщений: 5,989 Записей в блоге: 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