Найти минимальное положительное значение

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;

Редактировать: Извините, что нужно, если нет положительных чисел. Я думал, что у меня там было раньше, но, должно быть, пропустил это.

Answer 1

Трудно поверить, что Delphi все еще ограничен двумя значениями в функции Min. : - (

В Python вы можете настроить функцию для работы с любым количеством аргументов, например так:

def PosMin(*numbers):
    try:
        return min(num for num in numbers if num > 0)
    except:
        return 0

К сожалению, функция "min" вызывает исключение, если она заканчивается без значений (например, пустой список или в этом случае без чисел> 0), поэтому исключение должно быть перехвачено. Есть предложение для следующей версии python добавить значение дозорного, и похоже, что оно будет принято. В этом случае код был бы

return min (num for num in numbers if num > 0, sentinel=0)

без необходимости обработки исключений.

Answer 2

Я вижу слишком много строк кода для тех, кто пытается решить общую проблему в C #. Если значения IEnumerable<int>, то

values.Select(v => (int?)v)
      .Where(v => v > 0)
      .Min() ?? 0;

возвращает наименьшее положительное значение в values, если оно существует, в противном случае возвращается 0. Здесь я использую тот факт, что Enumerable.Min(IEnumerable<int?>) вернет null, если последовательность пуста. Итак, мы отфильтровываем неположительные значения, а затем находим минимум. Если все значения не положительны, мы получим ноль по желанию и в противном случае найдем минимум положительных значений.

Answer 3

Вот то, что я придумал, подумав об этом немного больше

Result := 0;
if value1 > 0 then
  Result := value1;
if (value2 > 0) and ((Result = 0) or (value2 < Result)) then
  Result := value2;
if (value3 > 0) and ((Result = 0) or (value3 < Result)) then
  Result := value3;

Конечно, если у вас есть список, чем более универсальные алгоритмы, тем лучше.

Answer 4

C # версия, которая охватывает все основы (я думаю):

public int GetMinimumPositiveValue(IEnumerable<int> values)
{
    int result = int.MaxValue;
    bool hasPositiveValue = false;

    foreach (int value in values)
    {
        if(value == 1) { return value; } 

        if(value > 0)
        {
            hasPositiveValue = true;

            if(value < result)
            {
                result = value;
            }
        }
    }

    return hasPositiveValue ? result : 0;
}

Answer 5

//return the smallest non-zero positive number, or null.
//relying on Min or Max is considered cheating.
public static int? smallestNonZeroPositiveNumberOfThree(
    int val1, int val2, int val3)
{
    //we have no guarantee that any of the 3 inputs will be positive
    int? result = null;
    if (val1 > 0) 
    {
        result = val1; 
        if (val2 > 0 && val2 < result) { result = val2; }
        if (val3 > 0 && val3 < result) { result = val3; }
    }
    else if (val2 > 0)
    {
        result = val2; 
        if (val3 > 0 && val3 < result) { result = val3; }
    }
    else if (val3 > 0)
    {
        result = val3; 
    }
    return result;
}

Answer 6

Это C #

public int GetSmallestPositive(IList<int> pValues)
{
    if(pValues == null)
    {
        throw new ArgumentNullException("pValues");
    }
    int _negNumCount = 0;
    int _smallest = int.MaxValue;
    for(int i = 0; i < pValues.Count; ++i)
    {
        if(pValues[i] < _smallest)
        {
            if(pValues[i] <= 0)
            {
                ++_negNumCount;
                continue;
            }
            _smallest = pValues[i];
            if(_smallest == 1)
            {
                return 1;
            }
        }
    }
    return (_negNumCount == pValues.Count) ? 0 : _smallest;
}

В этом случае и в вашем примере я использую целые числа, поэтому 1 - это наименьшее ненулевое число. Пока вы помещаете ваши целые в список, он будет работать с любым количеством значений.

Редактировать: Исправлено возвращать 0, если список полон отрицательных чисел. Бросьте исключение, если pValues ​​является нулем.

Answer 7

Это работает независимо от типа элементов массива

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

Answer 8

В Haskell, как обычно, проще всего решить общую проблему, а затем объявить особый случай.

foo xs = let xs1 = filter (>0) xs in if null xs1 then 0 else minimum xs1

foo3 x1 x2 x3 = foo [x1, x2, x3]

Answer 9

Ниже приведена версия С решения проблемы в посте с вопросом, но исправлен случай, когда все значения имеют значение MaxInt ...

int foo(int value1, int value2, int value3)
{
    int value1Temp, value2Temp, value3Temp, tempMax;
    value1Temp = max(value1, 0);
    value2Temp = max(value2, 0);
    value3Temp = max(value3, 0);
    tempMax = value1Temp | value2Temp | value3Temp;
    if (value1Temp == 0) { value1Temp = tempMax; }
    if (value2Temp == 0) { value2Temp = tempMax; }
    if (value3Temp == 0) { value3Temp = tempMax; }
    return min(value1Temp, min(value2Temp, value3Temp));
}

Также возможно сделать это без ветвления, так как min и max могут быть реализованы как операции без ветвей:

int min(int x, int y)
{
    return y + ((x - y) & -(x < y));
}

int max(int x, int y)
{
    return x - ((x - y) & -(x < y));
}

int foo(int value1, int value2, int value3)
{
    int value1Temp, value2Temp, value3Temp, tempMax, mask;
    value1Temp = max(value1, 0);
    value2Temp = max(value2, 0);
    value3Temp = max(value3, 0);
    tempMax = value1Temp | value2Temp | value3Temp;
    mask = -(value1Temp > 0);
    value1Temp = (value1Temp & mask) | (tempMax & ~mask);
    mask = -(value2Temp > 0);
    value2Temp = (value2Temp & mask) | (tempMax & ~mask);
    mask = -(value3Temp > 0);
    value3Temp = (value3Temp & mask) | (tempMax & ~mask);
    return min(value1Temp, min(value2Temp, value3Temp));
}

Для получения дополнительной информации о том, почему вы когда-либо захотите это сделать, см .: Является ли "Если" дорогим? и Битовые хаки Twiddling .

Редактировать: Заткнуло мою более раннюю попытку решения без ответвлений, которое фактически не работало. Добавлено новое бесплатное решение, которое должно работать.

Answer 10

function MinPositive(const AIntegers: array of Integer): Integer;
var
  LoopI: Integer;
  LFirstPositivePos: Integer;
begin
  Result := 0;
  LFirstPositivePos := MaxInt;
  for LoopI := Low(AIntegers) to High(AIntegers) do
  begin
    if (AIntegers[LoopI] > 0) then
    begin
      Result := AIntegers[LoopI];
      LFirstPositivePos := LoopI;
      Break;
    end;
  end;

  for LoopI := LFirstPositivePos to High(AIntegers) do
  begin
    if (AIntegers[LoopI] > 0) and (AIntegers[LoopI] < Result) then
    begin
      Result := AIntegers[LoopI];
    end;
  end;
end;

function MinPositive3(const I1, I2, I3: Integer): Integer;
begin
  Result := MinPositive([I1, I2, I3]);
end;