Алгоритм нахождения числа минимальной ненулевой величины в последовательности чисел

Question

Представьте, что у нас есть последовательность чисел, поступающих в последовательном порядке (всего N чисел).Как разработать алгоритм O (N) однопроходного (то есть во время прибытия последовательности), чтобы найти число (и его положение в последовательности) минимальной ненулевой величины?Обратите внимание, что стандартный простой алгоритм здесь не работает, поскольку начальное число может быть нулевым.

Answer 1

Один из способов решить эту проблему - смоделировать его как некий конечный автомат с двумя состояниями. В исходном состоянии вы еще не видели ненулевых значений, и поэтому ответ таков: «нет числа, отвечающего этому критерию». В этом состоянии каждый раз, когда вы видите ноль, вы остаетесь в этом состоянии. Для ненулевого значения запишите это значение и перейдите в следующее состояние. Это следующее состояние означает: «Я видел хотя бы одно ненулевое значение, и теперь мне нужно отслеживать наименьшее значение, которое я видел». Получив здесь, всякий раз, когда вы получаете ненулевое значение в качестве входных данных для алгоритма, вы сравниваете его величину с величиной значения с наименьшим ненулевым значением, которое вы видели, а затем сохраняете меньшее из двух.

Простая реализация этого на C-подобном языке может выглядеть так:

bool seenNonzeroValue = false;
double minValue; /* No initializer necessary; we haven't seen anything. */

while (MoreDataExists()) {
    double val = GetNextElement();

    /* If the value is zero, we ignore it. */
    if (val == 0.0) continue;

    /* If the value is nonzero, then the logic depends on our state. */
     *
     * If we have not seen any values yet, then record this value as the first
     * value we've seen.
     */
    if (!seenNonzeroValue) {
        seenNonzeroValue = true;
        minValue = val;
    }
    /* Otherwise, keep the number with the smaller magnitude. */
    else {
        if (fabs(val) < fabs(minValue))
             minValue = val;
    }
}

/* If we saw at least one value, report it.  Otherwise report an error. */
if (seenNonzeroValue)
    return minValue;
else
    ReportError("No nonzero value found!");

Надеюсь, это поможет!

Answer 2

Вам не нужно отслеживать, видели ли вы ненулевое значение или нет.Вместо этого вы можете использовать значения часового.Адаптация кода из ответа @ templatetypedef :

size_t pos = 0, minpos = -1; // track position as per the question requirements
double minValue = POSITIVE_INFINITY; // e.g., `1/+0.`

for ( ; MoreDataExists(); ++pos) {
  double val = GetNextElement();

  if (val and fabs(val) <= fabs(minValue)) { // skip +0, -0; update minValue 
    minpos   = pos;
    minValue = val;
  }
}

if (minpos != -1) 
  // found non-zero value with a minimal magnitude
  return make_pair(minpos, minValue);
else if (pos == 0)
  ReportError("sequence is empty");
else
  ReportError("no nonzero value found");

Пример на C ++

#include <algorithm>
#include <cmath>
#include <iostream>
#include <limits>

typedef double val_t;
typedef double* it_t;

int main () {
  val_t arr[] = {0, 0, 1, 0, 0, 2, 0}; // input may be any InputIterator
  it_t pend = arr + sizeof(arr)/sizeof(*arr);

  val_t sentinel = std::numeric_limits<val_t>::infinity();
  it_t pmin = &sentinel;

  for (it_t first = arr; first != pend; ++first)
    // skip +0,-0; use `<=` to allow positive infinity among values
    if (*first and std::abs(*first) <= std::abs(*pmin)) 
      pmin = first;

  if (pmin != &sentinel)
    std::cout << "value: " << *pmin << '\t'
              << "index: " << (pmin - arr) << std::endl;
  else
    std::cout << "not found" << std::endl;
}

Вывод

value: 1    index: 2

Answer 3

Вам необходимо рассмотреть возможные случаи, связанные с обработкой каждого числа в последовательности, т. Е. Оно равно нулю или не равно нулю, а если оно не равно нулю, то первое ненулевое или нет?Тогда имейте дело с алогритом в каждом случае.Я бы рекомендовал использовать логический флаг для отслеживания последнего случая.