c# - 算法改进

Question

我的求职面试任务是:

找到一个满足条件的数组项:删除后，剩余项的乘积最高。例如:-5, -3, -1, 4, 6 => -1

我的解决方案被认为不够优化。你能给我一些关于算法改进的建议吗？

我的解决方案是:

public int FindRequiredValue(int[] IntArray)
    {
        try
        {
            Array.Sort(IntArray);

            var first = IntArray.First();
            var last = IntArray.Last();

            if (first >= 0)
                return first;
            else
                if (last < 0)
                    return (IsEven(IntArray.Count()) ? first : last);
                else
                {
                    if (last == 0)
                    {
                        var lastindex = IntArray.Count() - 1;
                        if (IntArray[lastindex - 1] == 0)
                            return first;
                        else
                            return IsEven(lastindex) ? 0 : first;
                    }
                    else
                    {
                        var firstpositiveindex = IntArray.Select((x, i) => new { element = x, index = i }).First(y => (y.element > 0)).index;

                        if (IntArray[firstpositiveindex - 1] < 0)
                            return IsEven(firstpositiveindex) ? IntArray[firstpositiveindex] : IntArray[firstpositiveindex - 1];
                        else
                            if (IntArray[firstpositiveindex - 2] < 0)
                                return IsEven(firstpositiveindex - 1) ? 0 : first;
                            else
                                return first;
                    }
                }
        }
        catch (Exception ex)
        {
            throw;
        }
    }

请注意，所有非空检查、溢出等。在调用函数之前进行检查。

更新:可能的方式:排序等，循环等；还有其他想法吗？

Answer 1

您不需要对数组进行排序，这需要 O(n*log(n)) 复杂度；您可以使用 O(n) 解决方案。这就是为什么，恕我直言，您的代码次优。可能的实现:

public int FindRequiredValue(int[] value) {
  if (Object.ReferenceEquals(null, value))
    throw new ArgumentNullException("value");
  else if (value.Length <= 0)
    throw new ArgumentException("Empty arrays can't be proceeded.", "value");

  // Algorithm:
  // if the array contains odd negative numbers print out the maximum among them:
  //   {-1, -2, -3, 4, 5} => -1
  // if the array contains even negative numbers print out the smallest non-negative one:
  //   {-1, -2, 4, 5} => 4
  // if array contains even negative numbers and no non-negative numbers print out the
  // smallest negative one 
  //   {-1, -2, -3, -4} => -4

  int max_Negative = 0;
  int min_Negative = 0;
  int min_NonNegative = -1;
  int negativeCount = 0;

  foreach (int v in value) {
    if (v < 0) {
      negativeCount += 1;

      if ((v > max_Negative) || (max_Negative == 0))
        max_Negative = v;

      if ((v < min_Negative) || (min_Negative == 0))
        min_Negative = v;  
    }
    else {
      if ((v < min_NonNegative) || (min_NonNegative == -1))
        min_NonNegative = v; 
    }  
  }

  if ((negativeCount % 2) == 1)
    return max_Negative;
  else if (min_NonNegative != -1)
    return min_NonNegative;
  else
    return min_Negative; 
}