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

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

Восстановить пароль Регистрация
 
Damaks
18 / 10 / 1
Регистрация: 02.09.2010
Сообщений: 235
02.12.2012, 16:42     Выбрать n максимальных элементов из массива #1
Есть структура:
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++
Определение максимальных элементов массива (С++) C++
C++ Вывести количество максимальных элементов массива
Количество максимальных элементов массива C++
C++ Найти количество максимальных элементов массива
Поиск максимальных элементов в столбцах двумерного массива C++
C++ Дан массив а, состоящий из n целых чисел (n < = 100). Найти количество максимальных элементов массива
C++ Нахождение наибольшего из максимальных элементов по столбцам двоичного массива
C++ Задача на обработку массива: поиск максимальных и минимальных элементов, перестановка
C++ Найти произведение индексов L максимальных элементов массива
C++ Нахождение 3 максимальных элементов массива

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Buckstabue
 Аватар для Buckstabue
175 / 124 / 6
Регистрация: 12.01.2012
Сообщений: 624
02.12.2012, 16:56     Выбрать n максимальных элементов из массива #2
Damaks, а что значит
Цитата Сообщение от Damaks Посмотреть сообщение
получить N элементов с максимальным num в порядке убывания
?
Они должны находиться в дополнительной памяти или их надо выводить? Если первое, то я мог бы предложить создать вспомогательный массив индексов размерности N, все таки индексы хранить более "дешево", чем копии структур. Или указатели на эти структуры.
Damaks
18 / 10 / 1
Регистрация: 02.09.2010
Сообщений: 235
02.12.2012, 17:05  [ТС]     Выбрать n максимальных элементов из массива #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     Выбрать n максимальных элементов из массива #4
Цитата Сообщение от Damaks Посмотреть сообщение
Если реализовывать дополнительным массивом, то какой массив лучше?
после ввода N создать массив с размером N.

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

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

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