寻找最小正值

Question

如何找到固定数量（在这种情况下为3）的值中最小的非零正数或者在没有正数时返回0，哪种算法最好呢？

我的朴素方法如下（使用Delphi编写，但你可以使用任何你喜欢的语言），但我认为还有更优雅的方法。

value1Temp := MaxInt;
value2Temp := MaxInt;
value3Temp := MaxInt;

if ( value1T > 0) then
  value1Temp := value1;
if ( value2 > 0) then
  value2Temp := value2;
if ( value3 > 0) then
  value3Temp  := value3;

Result := Min(value1Temp, Min(value2Temp, value3Temp));
if Result = MaxInt then
  Result := 0;

编辑：抱歉，如果没有正数，则添加所需内容。我以为之前已经加进去了，但可能错过了。

- Ray

---

当三个元素都是MaxInt时，您的代码无法正常工作。 - isekaijin

好主意。我可以检查这三个值是否为零，如果是就提前返回（但我知道它们不会是 MaxInt）。 - Ray

如果三个值都是MaxInt，那么MaxInt就是列表中最小的非零正值...对吗？ - Troy Howard

是的，没错。但是上面的代码会返回0，而不是MaxInt。 - Ray

Answer 1

我会这样做：

结果 := 最大整数;
如果值1 > 0，则结果 := 最小值(结果, 值1);
如果值2 > 0，则结果 := 最小值(结果, 值2);
如果值3 > 0，则结果 := 最小值(结果, 值3);
如果结果 = 最大整数，则结果 := 0;

如果您想在循环中使用任意数量的问题，则：

结果 := 最大整数;
对于 I := 1 到 N do
   如果值[I] > 0，则结果 := 最小值(结果, 值[I]);
如果结果 = 最大整数，则结果 := 0;

如果您想让值数组为零基索引，请将for循环更改为：0到N-1

我认为这段代码非常清楚地说明了正在进行的操作。

在这种简单情况下，将"then"语句放在同一行使代码看起来更清晰，但是如果您觉得有必要，可以将"then"语句缩进到下一行。

- lkessler

Answer 2

我会做一个小循环（这是用C语言写的，我不是Delphi的人）：

int maxPositiveValue(int *number, int listSize)
{
    int i, result = 0;

    for(i = 0; i < listSize; i++)
    {
        if(number[i] > 0 && (number[i] < result || result == 0))
            result = number[i];
    }

    return result;
}

这段代码的优点是非常易读，可以轻松扩展以处理任何长度的值列表。

更新：我已根据下面收到的评论更改了代码。

新代码有点复杂，但现在可以处理以下情况：

1. 列表不包含正整数（返回0）。 2. 列表包含一个或多个INT_MAX的出现次数。 3. 任意长度的列表。

- Adam Pierce

---

如果您的列表中充满了负数，答案就是INT_MAX。如果您的列表中充满了INT_MAX，答案仍然是INT_MAX。 - isekaijin

谢谢您的建议。我已经修复了代码，除了所有输入都是INT_MAX的情况。我认为这是一个极端边缘条件，修复它会降低代码的可读性。 - Adam Pierce

现在，如果你的列表里全是INT_MAX，答案将会是零，这会更糟。 - isekaijin

这对于三个小数字来说有些过度了。 - csl

需要进行编辑： 结果=数字[0]; //第一行 并删除最后一个条件。 - Sridhar Iyer

Answer 3

以下是一个Delphi函数，您觉得如何：

function LowestPositiveInt(IntArr : array of Integer):Integer;
var
  iX : integer;
  bValid : boolean;
begin
  Result := MaxInt;
  bValid := False;
  for ix := 0 to High(IntArr) do
    if (IntArr[ix] > 0) then
      begin
        bValid := true;
        if (IntArr[iX] < Result) then
          Result := IntArr[ix];
      end;
  if not bValid then
    Result := 0;
end;

然后像下面这样调用：

ShowMessage(IntToStr( LowestPositiveInt([5,2,3,-1,12]) ));

这应该返回2。 这种方法的优点是数组可以包含任意数量的项，包括整数变量...因此，使用上面的示例，您可以说：

Result := LowestPositiveInt( [ Value1, Value2, Value3 ] );

编辑 已更新以处理 LowestPositiveInt([MaxInt，MaxInt，MaxInt]) 场景。

- skamradt

Answer 4

我不懂Delphi，但是这里有一个Ruby的快速解决方案（假设数字在列表中）

[1,2,42,-12].delete_if{|n| n <= 0 }.min || 0

从算法上来说，你需要删除所有的负数（或0），然后找到最小值。如果没有正数元素，[].min 返回 nil，所以最终的 || 0 将会返回请求的“0”作为答案。

- zenazn

---

那是Ruby中不错的一行代码。不幸的是，它不容易转换成Delphi。 - lkessler

Answer 5

在DELPHI中，如果您的域是整数，并且如果您可以将参数适配为longints，并且如果您可以避免传递最小整数（$80000000），那么这将给您所需的结果而不需要任何条件分支：

function cmMinInt( XX, YY, ZZ : longint ) : longint;
begin
   result := max(0,longint(
   min(longint((XX-1) xor $80000000),
   min(longint((YY-1) xor $80000000),
   longint((ZZ-1) xor $80000000)
   )) xor $80000000)+1);
end;

该技术依赖于长整型的可逆无损重映射，以使我们感兴趣的范围——从1到MAXINT的整数保持有序并占据最低值。简单地切换符号位几乎可以得到我们需要的结果，除了我们不想在较低范围内包括0。先减去1（然后再加回来）就可以解决这个问题。这里使用的异或运算扩展了两个操作数到int64，这需要一个显式转换回longint，以便min函数产生正确的结果。最后，如果所有操作数都为负，最小值将在上限范围内找到，并且答案将为负。在这种情况下，我们希望答案为0，因此我们只需使用max函数进行截取即可。

以下是相同的数学公式，为了更易读而分成多个语句：

function cmMinInt( XX, YY, ZZ : longint ) : longint;
begin
   // swap ordinal coding for range MININT..0 with range 1..MAXINT
   XX := XX-1;             // move region division to between 0 and 1
   XX := XX xor $80000000; // swap regions, preserving ordering
   XX := longint(XX);      // cram back into signed 32-bit
   // similarly with YY and ZZ
   YY := longint((YY-1) xor $80000000);
   ZZ := longint((ZZ-1) xor $80000000);
   // find min of three recoded values
   result := min(XX,min(YY,ZZ));
   // swap ordering back again
   result := result xor $80000000;  // swap regions, preserving ordering
   result := result+1;              // move region division back home
   result := longint(result);       // cram back into signed 32-bit
   // if all three were neg, result at this point is neg -- clip to zero
   result := max(0,result);
end;

-阿尔.

- A. I. Breveleri

---

我猜当我们要求“最好”的时候，却没有说明“最好是在什么方面”，就会得到这样的结果。 - Disillusioned

Answer 6

我同意Adam的观点。如果你只需要在一个容器中找到最小的自然数，那么算法上你不会比线性搜索更快。

他的代码应该运行得很快，很可能在x86中被翻译成CMOV，因此for循环内部的if语句也不会花费太多时间。

如果你最终想要按顺序列出所有非零数字，那么当然最好先排序，然后再切片。

- Calyth

---

有一个小优化可以实现，即在扫描循环中如果值为1，则退出循环（因为它是大于零的最小整数，所以默认情况下优先于其他任何值）。 - Troy Howard

Answer 7

你是在寻求美观还是速度？

如果是后者，我想不出有什么方法可以在应用程序中执行足够多次的测试以便被检测到：这并不重要。

祝好！

- Richard Haven

Answer 8

如果你处理的是非固定数量的值，那么你需要一个选择算法。

然而，如果你的代码只需要检查三个值，你应该避免使用循环和特定的算法，而是集中精力进行微观优化——尤其是尽可能少的分支。

在Hacker's Delight的第4章中有一些关于这方面的内容，你可以将有符号整数强制转换为无符号整数以减少分支的数量。这在下面的C代码中的函数smallest_v2()中完成：

#include <stdio.h>
#include <limits.h>

int smallest_v1(int a, int b, int c)
{
        int min = INT_MAX;

        min = a>0 && a<min ? a : min;
        min = b>0 && b<min ? b : min;
        min = c>0 && c<min ? c : min;
}

// See Hacker's Delight, chapter 4.
int smallest_v2(int a, int b, int c)
{
        int min = INT_MAX;

        if ( (unsigned) a < min ) min = a;
        if ( (unsigned) b < min ) min = b;
        if ( (unsigned) c < min ) min = c;

        return min;
}

int main()
{
        printf("min v1: %d\n", smallest_v1(-10, 7, 3));
        printf("min v2: %d\n", smallest_v1(-10, 7, 3));
}

基本上，这本书说如果你想检查是否

1 <= i <= 10

那么这就相当于进行无符号比较

(unsigned)(i - 1) <= 9

这本书还提供了一个证明。你可以在代码中获得更好的分支预测。你应该编写一个测试程序并计时。

- csl

Answer 9

Result := Min(IfThen(Value1 > 0, Value1, MAXINT), 
              Min(IfThen(Value2 > 0, Value2, MAXINT),
                  IfThen(Value3 > 0, Value3, MAXINT)));

循环不会起作用，如果输入不是一个列表/数组，根据问题。

从问题中不清楚函数在三个都不为正且非零时应该做什么。

- Craig Stuntz

---

这样行吗？如果Value1是5，而Value2和Value3都是0，似乎我仍然会得到零。 - Ray

把它们放进一个数组里，然后使用循环算法。 ;) - Troy Howard

抱歉，我以为在我的问题中已经表明了如果没有正数则返回零。我已经编辑了问题。 - Ray

Answer 10

无论数组元素的类型是什么，这都可以工作。

template <typename T>
T min_pos(T* a, int n)
{
    int i /* = 0 */ /* Edit: commented this out */;

    // Find the first positive element in the array
    for (i = 0; i < n; ++i)
        if (a[i] > 0)
            break;

    // If no positive element was found, return 0
    if (i == n)
        return 0;

    T res = a[i];

    // Search the rest of the array for an element
    // that is positive yet smaller than res
    for (++i; i < n; ++i)
    {
        if ((a[i] > 0) && (a[i] < res))
            res = a[i];
    }

    return res;
}

- Eduardo León

---

对于用户定义类型，通常会定义运算符 < 而不是运算符 >。你的代码要求类型 T 从 int 进行转换。另外请注意，这是一个 Delphi 问题，而不是 C++。 - Rob Kennedy

我并不担心语言问题，因为这些简单的算法翻译起来相当容易。 - Ray

Rob，我的代码不需要类型从int进行转换。它也适用于doubles。 - isekaijin