Индекс вектора, содержащий глобальный минимум - PullRequest
Новая
       20

Индекс вектора, содержащий глобальный минимум

0 голосов
/ 31 мая 2018

Учитывая вектор векторов, существует ли оптимальный способ определить индекс вектора, который содержит глобальный минимум?Что такое сложность в обозначении Big-O? 

#include <algorithm>
#include <iostream>
#include <vector>

unsigned getMinimumIndex(std::vector<std::vector<unsigned>> const& a) {

  if (!a.size())
    return 0;

  unsigned ret = 0; unsigned temp; unsigned global = 1 << 31;
  for (std::size_t idx = 0; idx < a.size(); ++idx) {
    if ((temp = *std::min_element(std::begin(a[idx]), std::end(a[idx]))) < global) {
      global = temp;
      ret = idx;
    }
  }
  return ret;
}

int main() {
  std::vector<std::vector<unsigned>> a = {{2, 4, 6, 8}, {3, 9, 5, 7},
                                          {3, 4, 4, 3}, {2, 8, 3, 2},
                                          {4, 4, 4, 0}, {1, 2, 3, 4}};
  std::cout << getMinimumIndex(a);  // 4-th vector posseses the value '0'
  return 0;
}

1 Ответ

0 голосов
/ 31 мая 2018

Поскольку ни ваши векторы, ни числа внутри вектора не отсортированы , вы должны проверять каждое число на наименьшее значение.Таким образом, вы получаете сложность O (n) .

. Вы можете использовать итераторы, как вы, или просто использовать 2 для циклов и получить доступ к вектору с помощью [i] [j] (что должно быть незначительно быстрее из-за отсутствия служебной информации от итераторов).

Кроме того - поскольку у вас есть только unsigned int, вы можете прерваться, как только найдете 0.

...