algorithm - 数列内の最小の非ゼロの大きさの数を見つけるアルゴリズム

Question

順番に到着する一連の数字があるとします (合計で N 個の数字)。最小の非ゼロの大きさの数 (およびシーケンス内の位置) を見つけるためのワンパス (つまり、シーケンス到着中) O(N) アルゴリズムを開発する方法は? 初期数がゼロになる可能性があるため、標準の単純なアルゴリズムはここでは機能しないことに注意してください。

Answer 1

ゼロ以外の値を見たかどうかを追跡する必要はありません。代わりにセンチネル値を使用できます。@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");

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 2

シーケンス内の各数値の処理に関連する可能性のあるケースを考慮する必要があります。つまり、それはゼロか非ゼロか、非ゼロの場合は最初の非ゼロかどうかです。次に、アルゴリズムに各ケースを処理させます。後者のケースを追跡するには、論理フラグを使用することをお勧めします。