Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.75/4: Рейтинг темы: голосов - 4, средняя оценка - 4.75
GraK
0 / 0 / 0
Регистрация: 22.01.2017
Сообщений: 34
Завершенные тесты: 1
1

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

17.05.2017, 16:01. Просмотров 824. Ответов 58
Метки нет (Все метки)

Есть вектор который заполняется рандомно. И нужно найти два элемента - самое большое значение и второе по величине. И главным условием сделать это с линейной сложностью.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.05.2017, 16:01
Ответы с готовыми решениями:

Написать программу с функцией для поиска экстремального (наибольшего или наименьшего) элемента массива
Написать программу с функцией для поиска экстремального (наибольшего или...

Поиска наибольшего по модулю элемента массива
Дан массив А и натуральное число n. Составить программу поиска наибольшего по...

Функция поиска наибольшего значение в одномерном массиве
Написал только функцию вывода массива: void PrintArray(){ srand (time (0));...

Функция: поиск экстремального (наибольшего или наименьшего) элемента массива
Написать программу с функцией для поиска экстремального числа(наибольшего или...

Дополнить описание для поиска наибольшего радиуса
Прошу помощи с заданием вот в таком готовом коде : #include <iostream>...

58
_Ivana
3233 / 1861 / 234
Регистрация: 01.03.2013
Сообщений: 5,091
Записей в блоге: 5
17.05.2017, 16:09 2
Так хоть 22 пробежки по контейнеру - это все равно линейная сложность
0
GraK
0 / 0 / 0
Регистрация: 22.01.2017
Сообщений: 34
Завершенные тесты: 1
17.05.2017, 20:10  [ТС] 3
пробовал сделать так
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
он не ищет дальше макс. эта функция подходит для отсортированного массива, а без сортировки нельзя?
0
_Ivana
3233 / 1861 / 234
Регистрация: 01.03.2013
Сообщений: 5,091
Записей в блоге: 5
17.05.2017, 21:14 4
Ну, сортировку в линейную сложность не уместишь, теоретический минимум n*log(n). Да и с сортировкой любой дурак решит. Значит, можно без сортировки
0
oldnewyear
411 / 409 / 157
Регистрация: 21.05.2016
Сообщений: 1,320
18.05.2017, 00:49 5
Используйте алгоритм Quickselect

Добавлено через 4 минуты
Хотя, зачем..
0
sourcerer
Модератор
Эксперт CЭксперт С++
4862 / 2043 / 325
Регистрация: 20.02.2013
Сообщений: 5,539
Записей в блоге: 24
Завершенные тесты: 1
18.05.2017, 08:15 6
Лучший ответ Сообщение было отмечено S_el как решение

Решение

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, всё равно иногда неправильно считает. Надо ещё подумать.
0
Manowar
1571 / 507 / 171
Регистрация: 12.03.2016
Сообщений: 1,930
Завершенные тесты: 1
18.05.2017, 08:28 7
gru74ik, у Вас находит второй максимальный после первого максимального,

а нужно, как я понял, просто второй элемент.
0
Manowar
1571 / 507 / 171
Регистрация: 12.03.2016
Сообщений: 1,930
Завершенные тесты: 1
18.05.2017, 08:30 8
Функция для поиска наибольшего и второго наибольшего элемента вектора
0
sourcerer
Модератор
Эксперт CЭксперт С++
4862 / 2043 / 325
Регистрация: 20.02.2013
Сообщений: 5,539
Записей в блоге: 24
Завершенные тесты: 1
18.05.2017, 08:43 9
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);
}
0
Manowar
1571 / 507 / 171
Регистрация: 12.03.2016
Сообщений: 1,930
Завершенные тесты: 1
18.05.2017, 08:47 10
gru74ik, сложность уже не линейная, не подходит к заданию.
Опять же Вы берете последние 2 элемента, а если у нас максимальных выпало 2 или 3. Второй по значению окажется опять максимальным.
0
sourcerer
Модератор
Эксперт CЭксперт С++
4862 / 2043 / 325
Регистрация: 20.02.2013
Сообщений: 5,539
Записей в блоге: 24
Завершенные тесты: 1
18.05.2017, 09:29 11
мановар, а если в 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, линейной или меньше? Или именно с линейной? То есть, если за время, меньше, чем линейное выполняется, то уже не годится?
0
sourcerer
Модератор
Эксперт CЭксперт С++
4862 / 2043 / 325
Регистрация: 20.02.2013
Сообщений: 5,539
Записей в блоге: 24
Завершенные тесты: 1
18.05.2017, 09:35 12
мановар, мда, тоже не подойдёт. Сложность создания сета из несортированного вектора больше, чем линейная:
0
Миниатюры
Функция для поиска наибольшего и второго наибольшего элемента вектора  
Manowar
1571 / 507 / 171
Регистрация: 12.03.2016
Сообщений: 1,930
Завершенные тесты: 1
18.05.2017, 09:54 13
Лучший ответ Сообщение было отмечено gru74ik как решение

Решение

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");
}
1
MrGluck
Модератор
Эксперт CЭксперт С++
8086 / 4939 / 1431
Регистрация: 29.11.2010
Сообщений: 13,395
18.05.2017, 09:56 14
Цитата Сообщение от _Ivana Посмотреть сообщение
Так хоть 22 пробежки по контейнеру - это все равно линейная сложность
А если размер контейнера равен 22?)
0
sourcerer
Модератор
Эксперт CЭксперт С++
4862 / 2043 / 325
Регистрация: 20.02.2013
Сообщений: 5,539
Записей в блоге: 24
Завершенные тесты: 1
18.05.2017, 10:02 15
мановар, как минимум тем, что алгоритм std::max_element вызывается дважды. Значит сложность будет O(2n), разве нет? Или это не так считается?

Плюс ещё цикл там у тебя. Это точно у тебя линейная сложность?
0
MrGluck
Модератор
Эксперт CЭксперт С++
8086 / 4939 / 1431
Регистрация: 29.11.2010
Сообщений: 13,395
18.05.2017, 10:13 16
Цитата Сообщение от gru74ik Посмотреть сообщение
вызывается дважды. Значит сложность будет O(2n), разве нет?
2N всё равно линейная, константные коэффициенты отбрасываются
3
Manowar
1571 / 507 / 171
Регистрация: 12.03.2016
Сообщений: 1,930
Завершенные тесты: 1
18.05.2017, 10:14 17
Цитата Сообщение от gru74ik Посмотреть сообщение
Значит сложность будет O(2n), разве нет? Или это не так считается?
gru74ik, не знаю (я самообучающийся, до сложностей алгоритмов еще не добрался), думал Вы подскажите.
Цитата Сообщение от gru74ik Посмотреть сообщение
Плюс ещё цикл там у тебя. Это точно у тебя линейная сложность?
Да вроде ничего навороченного, идем по порядку. Хотя ведь в самом алгоритме max_element заложены циклы и сравнения.
0
MrGluck
Модератор
Эксперт CЭксперт С++
8086 / 4939 / 1431
Регистрация: 29.11.2010
Сообщений: 13,395
18.05.2017, 10:19 18
мановар, если что асимптотическая сложность можно глянуть тут, в конце описания алгоритма/метода контейнера
Например, для max_element
Complexity
Linear in one less than the number of elements compared.
1
Manowar
1571 / 507 / 171
Регистрация: 12.03.2016
Сообщений: 1,930
Завершенные тесты: 1
18.05.2017, 10:28 19
MrGluck, да глянул и там и тут http://ru.cppreference.com/w/cpp/algorithm/max_element
Эти два сайта одни из основных. Такими темпами и по англикски скоро свободно переводить начну.
0
sourcerer
Модератор
Эксперт CЭксперт С++
4862 / 2043 / 325
Регистрация: 20.02.2013
Сообщений: 5,539
Записей в блоге: 24
Завершенные тесты: 1
18.05.2017, 11:44 20
Цитата Сообщение от 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 минуты
Предполагается, что вектор не состоит полностью из одинаковых элементов, не пуст, и не содержит только один элемент. Иначе нужно вставить соответствующие проверки.
0
18.05.2017, 11:44
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.05.2017, 11:44

Поиск наибольшего четного числа для каждого элемента
Помогите пожалуйста с задачкой.Для каждого элемента А(i,j) найти наиб.значение...

Рекурсивная функция для вычисления наибольшего значения в одномерном массиве
для вычисления наибольшего значения в одномерном массиве

Microsoft Visual Studio: Для каждой строки матрицы с нулевым элементом на главной диагонали вывести номер наибольшего элемента
Здравствуйте, прошу помощи. Вопрос жизни и смерти. В программировании вообще...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru