查找数字序列中最小非零幅度数的算法

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

中的示例

#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;
}

C++输出

value: 1    index: 2

Answer 3

您需要考虑处理序列中每个数字时涉及的可能情况，即：它是零还是非零，如果非零，它是否是第一个非零数字？然后用算法处理每种情况。我建议使用逻辑标志来跟踪后一种情况。