Algorithm to find the number of minimal nonzero magnitude within the sequence of numbers

Consider we have a sequence of numbers arriving in sequential order (N numbers in total). How to develop a one-pass (that is, during the sequence 开发者_JS百科arrival) O(N) algorithm to find the number (and it's position in the sequence) of minimal nonzero magnitude? Note that standard simple algorithm doesn't work here, since the initial number could be zero.

One way to solve this would be to model it as a sort of state machine with two states. In the initial state, you have not seen any nonzero values yet, and so the answer is "there is no number meeting this criterion." In this state, any time you see a zero you remain in the state. On a nonzero value, record that value and go to the next state. This next state means "I have seen at least one nonzero value, and now I need to keep track of the smallest value I've seen." Once you get here, whenever you get a nonzero value as input to the algorithm, you compare its magnitude to the magnitude of the value with the smallest nonzero magnitude that you've seen, then keep the smaller of the two.

A simple implementation of this in a C-like language might look like this:

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!");

Hope this helps!

You don't need to track whether you've seen non-zero value or not. You could use sentinel values instead. Adapting the code from the @templatetypedef' answer:

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");

Example in 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;
}

Output

value: 1    index: 2

You need to consider the possible cases involved in processing each number in the sequence, ie: is it zero or non-zero and if non-zero is it the first non-zero one or not? Then have the alogrithm deal with each case. I'd recommend using a logical flag to track the latter case.