Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
GraK
0 / 0 / 0
Регистрация: 22.01.2017
Сообщений: 34
Завершенные тесты: 1
#1

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

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

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

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

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

Функция поиска наибольшего значение в одномерном массиве - C++
Написал только функцию вывода массива: void PrintArray(){ srand (time (0)); const int n = 10; int a; for (int i = 0; i < n;...

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

Дополнить описание для поиска наибольшего радиуса - C++
Прошу помощи с заданием вот в таком готовом коде : #include <iostream> #include <vector> #include <algorithm> using namespace std; ...

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

58
_Ivana
3229 / 1857 / 157
Регистрация: 01.03.2013
Сообщений: 5,085
Записей в блоге: 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
3229 / 1857 / 157
Регистрация: 01.03.2013
Сообщений: 5,085
Записей в блоге: 5
17.05.2017, 21:14 #4
Ну, сортировку в линейную сложность не уместишь, теоретический минимум n*log(n). Да и с сортировкой любой дурак решит. Значит, можно без сортировки
0
oldnewyear
401 / 391 / 115
Регистрация: 21.05.2016
Сообщений: 1,269
18.05.2017, 00:49 #5
Используйте алгоритм Quickselect

Добавлено через 4 минуты
Хотя, зачем..
0
gru74ik
Модератор
Эксперт CЭксперт С++
4360 / 1936 / 210
Регистрация: 20.02.2013
Сообщений: 5,138
Записей в блоге: 22
18.05.2017, 08:15 #6
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
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
1278 / 472 / 97
Регистрация: 12.03.2016
Сообщений: 1,804
Завершенные тесты: 1
18.05.2017, 08:28 #7
gru74ik, у Вас находит второй максимальный после первого максимального,

а нужно, как я понял, просто второй элемент.
0
Manowar
1278 / 472 / 97
Регистрация: 12.03.2016
Сообщений: 1,804
Завершенные тесты: 1
18.05.2017, 08:30 #8
Функция для поиска наибольшего и второго наибольшего элемента вектора
0
gru74ik
Модератор
Эксперт CЭксперт С++
4360 / 1936 / 210
Регистрация: 20.02.2013
Сообщений: 5,138
Записей в блоге: 22
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
1278 / 472 / 97
Регистрация: 12.03.2016
Сообщений: 1,804
Завершенные тесты: 1
18.05.2017, 08:47 #10
gru74ik, сложность уже не линейная, не подходит к заданию.
Опять же Вы берете последние 2 элемента, а если у нас максимальных выпало 2 или 3. Второй по значению окажется опять максимальным.
0
gru74ik
Модератор
Эксперт CЭксперт С++
4360 / 1936 / 210
Регистрация: 20.02.2013
Сообщений: 5,138
Записей в блоге: 22
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
gru74ik
Модератор
Эксперт CЭксперт С++
4360 / 1936 / 210
Регистрация: 20.02.2013
Сообщений: 5,138
Записей в блоге: 22
18.05.2017, 09:35 #12
мановар, мда, тоже не подойдёт. Сложность создания сета из несортированного вектора больше, чем линейная:
0
Миниатюры
Функция для поиска наибольшего и второго наибольшего элемента вектора  
Manowar
1278 / 472 / 97
Регистрация: 12.03.2016
Сообщений: 1,804
Завершенные тесты: 1
18.05.2017, 09:54 #13
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
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Эксперт С++
7800 / 4844 / 754
Регистрация: 29.11.2010
Сообщений: 13,210
18.05.2017, 09:56 #14
Цитата Сообщение от _Ivana Посмотреть сообщение
Так хоть 22 пробежки по контейнеру - это все равно линейная сложность
А если размер контейнера равен 22?)
0
gru74ik
Модератор
Эксперт CЭксперт С++
4360 / 1936 / 210
Регистрация: 20.02.2013
Сообщений: 5,138
Записей в блоге: 22
18.05.2017, 10:02 #15
мановар, как минимум тем, что алгоритм std::max_element вызывается дважды. Значит сложность будет O(2n), разве нет? Или это не так считается?

Плюс ещё цикл там у тебя. Это точно у тебя линейная сложность?
0
18.05.2017, 10:02
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.05.2017, 10:02
Привет! Вот еще темы с ответами:

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

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

Нахождение наибольшего элемента в последовательности - C++
По структурам и алгоритмам дали задание, найти наибольшее число с помощью сложения чисел последовательности. Я набросал такой код. Но не...

Нахождение наибольшего элемента дерева - C++
Написать функцию, которая находит наибольший элемент дерева. Добавлено через 3 часа 56 минут помогитее((


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

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

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