Это интересный вопрос. Это, вероятно, было дано какой-то обучающей стороной. Это должно показать ученику, подумать о проблеме, прежде чем начинать кодирование. Следовательно, для меня это хороший вопрос.
Итак, давайте сначала рассмотрим наивный грубый подход
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
int main() {
// Inform the user what to do. On "competetive-coding" pages, all such output is not allowed
// You may delete the following line
std::cout << "\nEnter count of values and then the values itself: ";
// Read the values. will most probably be piped in (a.out < numbers.txt). Check, if that worked
if (int countOfValues{}; std::cin >> countOfValues) {
// In the following vector, we will take the user input, the indices to increase
std::vector<unsigned int>indices(countOfValues, 0U);
// Copy the calues from std::cin to our indices vector
std::copy_n(std::istream_iterator<unsigned int>(std::cin), countOfValues, indices.begin());
// -------------------------------------------------------------------------------------------
// Now the naive brute force approach
constexpr size_t VectorSize = 1'000'000;
// Here we will increase values at the given indices
std::vector<size_t> data(VectorSize, 0U);
// Increase all data at the given index
for (const size_t index : indices) {
if (index < VectorSize) data[index]++;
}
// We need some vector for the result
std::vector<size_t> result{};
// Generate result, copy values > 0
std::copy_if(data.begin(), data.end(), std::back_inserter(result), [](const int i) { return (i > 0); });
// Show result to the user:
std::cout << "\n\nResult is: ";
std::copy(result.begin(), result.end(), std::ostream_iterator<size_t>(std::cout, " "));
std::cout << "\n\n";
}
return 0;
}
Итак, что происходит сейчас? Простой ввод 1 999999 приведет к необходимости итерации по полному вектору размером 1 000 000. Хотя в нем есть только одна необходимая информация.
Кстати, такой вектор называется «разреженным» вектором. Большой размер, и только некоторые слоты заполнены. Эти векторы никогда не будут храниться как плоский большой вектор, но часто с некоторой структурой «разреженных» данных.
Далее мы немного посмотрим на задачу. И даже в нашем наивном решении мы увидим, что мы увеличиваем значение при данных индексах для всех связанных входных данных. И в конце мы подсчитываем заданные индексы.
Итак, мы получили от пользовательского ввода индексы и должны их подсчитать. В качестве структуры данных нам нужно что-то вроде:
index -> count
Для такой структуры данных у нас есть хорошее представление в STL. std::map, ассоциативный контейнер. Пожалуйста, смотрите здесь . count связан с index.
И что нам особенно нужно, это операция, чтобы добавить данные в std::map и получить доступ к этим данным, чтобы увеличить их. И, угадайте, у std::map есть такая функциональность? Это реализовано через operator[]. Если вы посмотрите здесь , то вы можете прочитать:
Возвращает ссылку на значение, сопоставленное с ключом, эквивалентным ключу, выполняя вставку, если такого ключа еще нет существовать.
Это означает, что если данные еще не находятся в std::map, они будут добавлены. И, независимо от того, был ли он только что добавлен или был в std::map, ссылка на эти данные будет возвращена. И это мы будем просто увеличивать.
result[index]++;
Кстати, это выглядит очень похоже на наивную версию, где мы написали:
data[index]++;
Но теперь мы увеличиваем просто необходимые значения.
С нашим демонстрационным вводом выше 1 999999 мы просто добавим ОДИН фрагмент данных.
Пожалуйста, посмотрите окончательное решение (одно из многих возможных решений):
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <map>
int main() {
// Inform the user what to do. On "competetive-coding" pages, all such output is not allowed
// You may delete the following line
std::cout << "\nEnter count of values and then the values itself: ";
// Read the values. will most probably be piped in (a.out < numbers.txt). Check, if that worked
if (int countOfValues{}; std::cin >> countOfValues) {
// In the following vector, we will take the user input, the indices to increase
std::vector<unsigned int>indices(countOfValues, 0U);
// Copy the calues from std::cin to our indices vector
std::copy_n(std::istream_iterator<unsigned int>(std::cin), countOfValues, indices.begin());
// -------------------------------------------------------------------------------------------
// Now the more algorithmic approach using a std::map
std::map<size_t, size_t> result{};
// Increase all data at the given index
for (const size_t index : indices) {
result[index]++;
}
// Show result to the user:
std::cout << "\n\nResult is:\n\n";
for (const auto& [index, counter] : result) std::cout << counter << " ";
std::cout << "\n\n";
}
return 0;
}