Форум программистов, компьютерный форум CyberForum.ru

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

Войти
Регистрация
Восстановить пароль
 
Damaks
18 / 10 / 1
Регистрация: 02.09.2010
Сообщений: 235
#1

Выбрать n максимальных элементов из массива - C++

02.12.2012, 16:42. Просмотров 583. Ответов 5
Метки нет (Все метки)

Есть структура:
C++
1
2
3
4
struct data {
    /* какте-то поля */
    uint32_t num;         // Число
};
есть массив этой структуры
C++
1
std::vector<data> mdata;
Задача - получить N элементов с максимальным num в порядке убывания. Получить их надо не меняя порядок следования элементов в массиве mdata. Подскажите как это правильно сделать?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.12.2012, 16:42
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Выбрать n максимальных элементов из массива (C++):

Определение максимальных элементов массива (С++) - C++
Всем добрый день) Задача следующая. Даны два массива, в одном 5 элементов, в другом 20. Определить индексы и значения максимальных...

Количество максимальных элементов массива - C++
Написал код рабочий по нахождению максимального элемента, но вот проблемка, не могу найти кол-во одинаковых максимальных элементов ...

Нахождение 3 максимальных элементов массива - C++
#include &lt;iostream&gt; #include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; using namespace std; int main() { int *arr; // указатель для...

Удаление максимальных элементов из массива - C++
Помогите пожалуйста написать программу на С. Задан массив действительных чисел a1,a2,...,an. Получить новую последовательность, выбросив...

Найти количество максимальных элементов массива - C++
Дан массив а,состоящий из n целых чисел (n&lt;=100).Найти количество максимальных элементов массива

Вывести количество максимальных элементов массива - C++
Доброго всем вечера, задали написать программу которая выводит количество максимальных элементов массива... Я еще не очень розбираюсь в с++...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Buckstabue
175 / 124 / 6
Регистрация: 12.01.2012
Сообщений: 624
02.12.2012, 16:56 #2
Damaks, а что значит
Цитата Сообщение от Damaks Посмотреть сообщение
получить N элементов с максимальным num в порядке убывания
?
Они должны находиться в дополнительной памяти или их надо выводить? Если первое, то я мог бы предложить создать вспомогательный массив индексов размерности N, все таки индексы хранить более "дешево", чем копии структур. Или указатели на эти структуры.
Damaks
18 / 10 / 1
Регистрация: 02.09.2010
Сообщений: 235
02.12.2012, 17:05  [ТС] #3
N например 5. num - число, у каждого элемента своё.
например имеем такую последовательность элементов со значением num:
6 10 1 5 9 8 5 5 3 5 8 2
На выходе надо получить:
10 9 8 8 6
Нужно либо выводить, либо дополнительный массив, не важно. Главное скорость должна быть максимальна. Если реализовывать дополнительным массивом, то какой массив лучше?
Issues
430 / 365 / 37
Регистрация: 06.08.2012
Сообщений: 961
02.12.2012, 17:10 #4
Цитата Сообщение от Damaks Посмотреть сообщение
Если реализовывать дополнительным массивом, то какой массив лучше?
после ввода N создать массив с размером N.

Добавлено через 1 минуту
и туда запихнуть N max элементов.
Damaks
18 / 10 / 1
Регистрация: 02.09.2010
Сообщений: 235
02.12.2012, 17:11  [ТС] #5
после ввода N создать массив с размером N.
Всмысле? У меня массив mdata уже содержет несколько миллионов элементов. Мне нужно выбрать из него несколько тысяч (N) с максимальным значением num. Я ничего не ввожу...

Добавлено через 1 минуту
Цитата Сообщение от SeregaC++ Посмотреть сообщение
и туда запихнуть N max элементов.
Их же еще выбрать как-то надо
Buckstabue
175 / 124 / 6
Регистрация: 12.01.2012
Сообщений: 624
02.12.2012, 18:48 #6
Damaks, выбираешь первые N элементов(точнее их индексы или указатели) и запихиваешь во вспомогательный массив. Сортируешь по желанию этот вспомогательный массив. Далее, начиная с N + 1 элемента, смотришь исходный массив и в случае нахождения элемента меньшего, чем во вспомогательном заменяешь больший элемент на меньший. Вообще я не вижу здесь оптимального алгоритма, где-то быстрее будет хранить индексы в массиве, где-то быстрее будет пробежаться N раз по всему массиву. По поводу более экономного расхода памяти можно поступить таким образом:
заводим переменные curMax, prevMax // текущий максимум и предыдущий максимум в векторе mdata
В конкретно данном случае prevMax можно сделать равным INT_MAX из стандартной библиотеки <climits>
обходим массив N раз и каждый раз рассматриваем только те значения, которые меньше prevMax. Среди этих значения ищем максимум и записываем его в curMax. после каждой внешней итерации выводим значение curMax и делаем prevMax = curMax
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.12.2012, 18:48
Привет! Вот еще темы с ответами:

Найти произведение индексов L максимальных элементов массива - C++
Для массива А(n) найти произведение индексов L максимальных элементов, где 0&lt;=n&lt;=45. Число L ввести с клавиатуры. Значения элементов...

Поиск максимальных элементов в столбцах двумерного массива - C++
Добрый вечер! Помогите пожалуйста решить задачу, я начинающий.. Сформировать векторы А и B, элементами которых являются максимальные...

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

Переставить местами выбранный элемент и первый из максимальных элементов массива - C++
3).Объединим первый и второй приёмы. Решив задачу, суть которой не в том, чтобы переставить местами два выбранных элемента, а в том, чтобы...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
02.12.2012, 18:48
Ответ Создать тему
Опции темы

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