Arhn - архитектура программирования

Как найти все индексы вектора‹vector‹int›› для минимального первого индекса

У меня есть двумерный вектор данных, который не отсортирован и содержит повторяющиеся элементы.

Как найти минимум и все индексы со значением?

Например, учитывая данные vector<vector<int>> mySol = {{3,1},{1,2},{4,5},{1,3},{1,2}}, я хочу найти {1,2}, {1,3} и {1,2}, которые дают минимальное значение 1 (на основе первого элемента) и индексы 2, 3 и 2.

Как улучшить следующий фрагмент кода? Для больших данных следующий код кажется медленным из-за sort:

vector<vector<int>> mySol = {{3,1},{1,2},{4,5},{1,3},{1,2}};
sort(mySol.begin(), mySol.end());

//print out shortest distance
cout << mySol[0][0] << endl;

//print out the number of shortest paths
int nShortest = 0;
for (int i = 0; i < mySol.size(); i++) {
    if (mySol[0][0] == mySol[i][0])
        nShortest += 1;
}
cout << nShortest << "  ";

//print out y-coordinates of the shortest paths in increasing order
for (int i = 0; i < nShortest; i++) {
    cout << mySol[i][1] << " ";
}
c++ c++11
25.12.2016

  • Вы хотите сравнить только первый элемент внутреннего вектора? 25.12.2016
  • Также похоже, что все ваши внутренние векторы имеют длину 2. Если это так, возможно, вы не хотите использовать для них std::vector. 25.12.2016
  • Сначала вы можете изменить свой первый цикл на for (int i = 0; i < mySol.size() && mySol[0][0] == mySol[i][0]; i++) { nShortest += 1;}. Не нужно перебирать весь вектор. 25.12.2016
  • Да, первый элемент — это значение для нахождения минимума, остальные — координаты. Кроме того, mySol в vector‹vector‹int›› на самом деле создается другой функцией некоторым образом mySol.push_back(). 25.12.2016

Ответы:


1

Вы можете выполнить работу за линейное время:

  • сначала найти минимум
  • затем повторите на минимумах.

Что-то типа:

auto cmp = [](const auto& lhs, const auto& rhs) { return lhs[0] < rhs[0]; }
auto minIt = std::min_element(mySol.begin(), mySol.end(), cmp);
auto eqToMin = [&](const auto& value) { return (*minIt)[0] == value[0]; }

for (auto it = minIt; it != mySol.end(); it = std::find_if(it + 1, mySol.end(), eqToMin)) {
    std::cout << (*it)[1] << std::endl;
}
25.12.2016

2

Спасибо Джарод! Основываясь на идее Джарода, я изменил код следующим образом. Используйте простой min и избегайте find_if. Это кажется быстрее, избегая сортировки и находя минимум.

vector<vector<int>> mySol = {{3,1},{1,2},{4,5},{1,3},{1,2}};
auto minIt = std::min(mySol.begin(), mySol.end());
cout << (*minIt)[0] << endl;

int nShortest = 0;
for (auto it = mySol.begin(); it != mySol.end(); ++it) {
    if ((*it)[0] == (*minIt)[0]) ++nShortest;
}
cout << nShortest << " ";

for (auto it = mySol.begin(); it != mySol.end(); ++it) {
    if ((*it)[0] == (*minIt)[0]) {
        cout << (*it)[1] << " ";
    }
}
25.12.2016
  • std::min не делает того, что вы ожидаете Демо. вам действительно нужно std::min_element. Для фильтрации это нормально, а nShortest неверно, так как теперь ввод не сортируется. 25.12.2016
  • Ты прав, Джарод42. min ведет себя не так, как я ожидал, поэтому необходимо использовать min_element. 26.12.2016
    • Новые материалы
    Коллекции публикаций по глубокому обучению
    Последние пару месяцев я создавал коллекции последних академических публикаций по различным подполям глубокого обучения в моем блоге https://amundtveit.com - эта публикация дает обзор 25..
    Представляем: Pepita
    Фреймворк JavaScript с открытым исходным кодом Я знаю, что недостатка в фреймворках JavaScript нет. Но я просто не мог остановиться. Я хотел написать что-то сам, со своими собственными..
    Советы по коду Laravel #2
    1-) Найти // You can specify the columns you need // in when you use the find method on a model User::find(‘id’, [‘email’,’name’]); // You can increment or decrement // a field in..
    Работа с временными рядами спутниковых изображений, часть 3 (аналитика данных)
    Анализ временных рядов спутниковых изображений для данных наблюдений за большой Землей (arXiv) Автор: Рольф Симоэс , Жильберто Камара , Жильберто Кейрос , Фелипе Соуза , Педро Р. Андраде ,..
    3 способа решить квадратное уравнение (3-й мой любимый) -
    1. Методом факторизации — 2. Используя квадратичную формулу — 3. Заполнив квадрат — Давайте поймем это, решив это простое уравнение: Мы пытаемся сделать LHS,..
    Создание VR-миров с A-Frame
    Виртуальная реальность (и дополненная реальность) стали главными модными терминами в образовательных технологиях. С недорогими VR-гарнитурами, такими как Google Cardboard , и использованием..
    Демистификация рекурсии
    КОДЕКС Демистификация рекурсии Упрощенная концепция ошеломляющей О чем весь этот шум? Рекурсия, кажется, единственная тема, от которой у каждого начинающего студента-информатика..