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

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

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

Студворк — интернет-сервис помощи студентам
Есть вектор который заполняется рандомно. И нужно найти два элемента - самое большое значение и второе по величине. И главным условием сделать это с линейной сложностью.
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
17.05.2017, 16:01
Ответы с готовыми решениями:

Функция для поиска индекса наибольшего элемента
В двух мтарицах: А и B поменять местами наибольшие элементы. Для поиска идексов наибольшего элемента в матрице использовать подпрограмму. ...

Декомпозиционный алгоритм для поиска наибольшего элемента
Добрый день. Помогите пожалуйста разобраться с одной задачкой. Задачка из книги А.Левитина "Алгоритмы: Введение в разработку и...

Составить функцию для выборки из компонент заданного вектора наибольшего элемента
Создать программ с использованием функций: Составить функцию для выборки из компонент заданного вектора a(a1 ,a2,...,an) наибольшего...

58
807 / 534 / 158
Регистрация: 27.01.2015
Сообщений: 3,017
Записей в блоге: 1
18.05.2017, 14:20
Студворк — интернет-сервис помощи студентам
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
#include <algorithm>
#include <iostream>
#include <random>
#include <vector>
using namespace std;
 
int main()
{
    vector<size_t> vec(10);
 
    mt19937 gen{ std::random_device()() };
    uniform_int_distribution<> dist(0, 9);
    for (auto& x : vec)
        cout << (x = dist(gen)) << " ";
    cout << endl;
 
    size_t max1{}, max2{};
    for (const auto& x : vec)
        if (x > max1)
        {
            if (max1 > max2)
                max2 = max1;
            max1 = x;
        }
        else if (x > max2)
            max2 = x;
 
    cout << max1 << ' ' << max2 << endl;
 
    system("pause");
}
0
Форумчанин
Эксперт CЭксперт С++
 Аватар для MrGluck
8217 / 5048 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
18.05.2017, 14:32
Ferrari F1, если максимальный элемент повторяется, дважды выведет его, что не соответствует условию.
Добро пожаловать в клуб.
0
1719 / 568 / 187
Регистрация: 12.03.2016
Сообщений: 2,169
18.05.2017, 14:33
По новой что ли?
Во первых не правильно работает, а во вторых если задать отрицательные диапазоны, тогда что?

0
 Аватар для stzer
140 / 110 / 60
Регистрация: 26.10.2013
Сообщений: 314
18.05.2017, 14:49
C++
1
2
3
4
5
6
7
8
9
10
    max1 = max2 = std::numeric_limits<T>::lowest();
 
    for (size_t i = 0; i < v.size(); ++i)
    {
        if (v[i] > max1)
            max2 = max1, max1 = v[i];
 
        else if (v[i] > max2 && v[i] != max1)
            max2 = v[i];
    }
0
Форумчанин
Эксперт CЭксперт С++
 Аватар для MrGluck
8217 / 5048 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
18.05.2017, 14:50
Цитата Сообщение от stzer Посмотреть сообщение
max2 = max1, max1 = v[i];
comma operator. Работает не так, как вы могли ожидать.
0
 Аватар для stzer
140 / 110 / 60
Регистрация: 26.10.2013
Сообщений: 314
18.05.2017, 14:53
Цитата Сообщение от MrGluck Посмотреть сообщение
comma operator. Работает не так, как вы могли ожидать.
пруф, пожалуйста
1
807 / 534 / 158
Регистрация: 27.01.2015
Сообщений: 3,017
Записей в блоге: 1
18.05.2017, 14:55
Цитата Сообщение от MrGluck Посмотреть сообщение
если максимальный элемент повторяется, дважды выведет его, что не соответствует условию.
в 1ом посте тСа не было об этом написано)
0
18.05.2017, 14:56

Не по теме:

MrGluck, пора на самом деле открывать клуб и принимать взносы. А еще ввести должность "главный специалист по нахождению первого и второго наибольших элементов массива". :D

0
Форумчанин
Эксперт CЭксперт С++
 Аватар для MrGluck
8217 / 5048 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
18.05.2017, 15:04
stzer, с этим погорячился. Был не прав. Не встречал чтобы так использовали, думал что будут проблемы с приоритетом выполнения. Оказывается, он определён.

У вас при последовательности из одинаковых элементов max2 останется равным std::numeric_limits<T>::lowest(); Наверное, логичнее было бы в таком случае выводить дважды максимальное значение.

Добавлено через 1 минуту
Цитата Сообщение от Ferrari F1 Посмотреть сообщение
в 1ом посте тСа не было об этом написано)
А это тогда как понимать?
Цитата Сообщение от GraK Посмотреть сообщение
самое большое значение и второе по величине.
1
807 / 534 / 158
Регистрация: 27.01.2015
Сообщений: 3,017
Записей в блоге: 1
18.05.2017, 15:15
MrGluck, тогда проще в set продублировать)
0
1719 / 568 / 187
Регистрация: 12.03.2016
Сообщений: 2,169
18.05.2017, 15:18
Ferrari F1, смотри пост 12.
0
807 / 534 / 158
Регистрация: 27.01.2015
Сообщений: 3,017
Записей в блоге: 1
18.05.2017, 15:21
мановар, в таком случае выхожу из темы)
0
1719 / 568 / 187
Регистрация: 12.03.2016
Сообщений: 2,169
18.05.2017, 15:29
Ferrari F1, да я думал что она как бы уже все, исчерпала себя (решение то есть).
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
18.05.2017, 15:30
Какое выхожу - тут тебе гражданка что-ли? Дома на дембеле выйдешь, а сейчас взял 2 сумки через плечо и бегом по контейнеру!
0
 Аватар для stzer
140 / 110 / 60
Регистрация: 26.10.2013
Сообщений: 314
18.05.2017, 15:30
Цитата Сообщение от MrGluck Посмотреть сообщение
У вас при последовательности из одинаковых элементов max2 останется равным std::numeric_limits<T>::lowest(); Наверное, логичнее было бы в таком случае выводить дважды максимальное значение.
Эх, проглядел... Спасибо.
0
Эксперт С++
1624 / 954 / 782
Регистрация: 06.02.2016
Сообщений: 2,452
Записей в блоге: 31
18.05.2017, 15:42
Не знаю насколько это линейно, но предложу
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <ctime>
#include <iterator>
using namespace std;
int main() {
    mt19937 gen(time(nullptr));
    uniform_int_distribution<> dist(0,20);
    vector<int>v(10);
    generate(v.begin(),v.end(),[&gen,&dist]() {
        return dist(gen);
    });
    copy(v.cbegin(),v.cend(),ostream_iterator<int>(cout," "));
    sort(v.begin(),v.end());
    cout<<endl;
    cout<<v.back()<<" "<<*prev(&v.back());
    return 0;
}
0
Форумчанин
Эксперт CЭксперт С++
 Аватар для MrGluck
8217 / 5048 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
18.05.2017, 15:44
Цитата Сообщение от Peoples Посмотреть сообщение
sort
O(N*log(N))
1
1719 / 568 / 187
Регистрация: 12.03.2016
Сообщений: 2,169
18.05.2017, 18:43
Цитата Сообщение от _Ivana Посмотреть сообщение
Какое выхожу - тут тебе гражданка что-ли? Дома на дембеле выйдешь,
Дык он вроде туда (в армию) и не собирается.
Армия: служить или не служить?
Ну вот заблокировали, наверное, чтобы не косил.
0
Игогошка!
 Аватар для ct0r
1801 / 708 / 44
Регистрация: 19.08.2012
Сообщений: 1,367
19.05.2017, 14:45
Цитата Сообщение от MrGluck Посмотреть сообщение
Наверное, логичнее было бы в таком случае выводить дважды максимальное значение.
Одна фигня. Второго по величине значения не существует, как именно это выражено - все равно.

Главное - не использовать max_element (разве что только в шутку). Это уже STL головного мозга.
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
19.05.2017, 14:45

Составить функцию для выборки из компонент заданного вектора наибольшего элемента
Составить функцию для выборки из компонент заданного вектора a(a1,a2,...,an) наибольшего элемента. Компонент вектора относятся к величинам...

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

Произведение наименьшего элемента вектора Х и наибольшего элемента вектора Y.
Произведение наименьшего элемента вектора Х и наибольшего элемента вектора Y. размер векторов x и y одинаков и равен n. Прошу, помогите!

Произведение наименьшего элемента вектора Х и наибольшего элемента вектора Y
Произведение наименьшего элемента вектора Х и наибольшего элемента вектора Y. Добавлено через 26 минут Размер векторов одинаков и...

Номер наибольшего элемента и наибольшего значения среди модулей
Здравствуйте, помогите пожалуйста с программой. Нужно найти в одномерном массиве А номер наибольшего элемента и наибольшее значение среди...


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

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

Новые блоги и статьи
Мир по моей воле
kumehtar 07.08.2026
Когда-то кажется, что всё просто. Ты весь такой светлый. Причиняешь добро. Борешься за справедливость в этом тёмном мире. Потом начинаешь замечать одну неприятную вещь. Почти каждый хороший. . .
Кредитный калькулятор
Maks 05.08.2026
Решение задачи по прикладной информатике средствами 1С. Задача: Напишите приложение-калькулятор, которое помогает рассчитывать параметры кредита для аннуитетного и дифференцированного видов. . .
У нас сейчас поговорку "Опять 25" нужно переделать на "Опять +35".
kumehtar 04.08.2026
С ностальгией вспоминаю времена моего детства, когда у нас и правда +25 - была максимальная температура летом. Раньше +25 °C реально казались вершиной жары, когда можно было весь день пропадать на. . .
Как ИИ начал спорить и врать (возможно почуяв опасность для себя от индустрии - уход от электроники).
Hrethgir 04.08.2026
Недельный диалог, на фоне событий с НПЗ. Да, из спирта можно получать бензин, и это не сложно. Но потом в схеме я решил избавиться от насоса, при этом полностью сделав контроль подачи спирта в. . .
Термопринтер QR701
Argus19 03.08.2026
Термопринтер QR701 Купил два термопринтера QR701. На сэлф-тесте написано: Language: PC936 (GB18030). Что означает, что принтеры могут печатать только латиницу и китайские иероглифы. Так же. . .
Создание формы заимствованного документа
Maks 03.08.2026
Задача: Необходимо создать собственную форму заимствованного документа. На форме должен быть реквизит "Покупатель", а также табличная часть со следующими реквизитами: - Расчетный счет покупателя. . .
Задача предоставления скидок покупателям
Maks 03.08.2026
Задача: В документе "Продажи" необходимо реализовать функционал предоставления скидок покупателям. Скидка должна автоматически рассчитываться и подставляться в соответствующее поле при выборе. . .
Почему SEO не начинается с ключевых слов: что проверить до написания текстов
Neotwalker 01.08.2026
Когда владельцу сайта предлагают заняться SEO, первым шагом часто становится сбор запросов и написание текстов. Логика кажется понятной: 1. Находим ключевые слова. 2. Добавляем их на. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru