1

考虑我们有一个按顺序到达的数字序列（总共 N 个数字）。如何开发一个单程（即在序列到达期间）O(N) 算法来找到最小非零幅度的数字（及其在序列中的位置）？请注意，标准简单算法在这里不起作用，因为初始数字可能为零。

4

3 回答 3

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

希望这可以帮助！

于 2011-03-14T07:32:47.637 回答
1

您不需要跟踪您是否看到了非零值。您可以改用哨兵值。改编来自@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
于 2011-03-14T12:11:29.360 回答
0

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

于 2011-03-14T07:06:57.677 回答