我的工作面试任务是:
发现一个数组项满足条件:将其删除后,剩余项的乘积将是最大的。 例如:-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;
}
}
请注意,所有非空检查、溢出等。在调用函数之前进行检查。
更新: 可能的方式:排序等、循环等;还有其他想法吗?
最佳答案
您不需要对数组进行排序,这需要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;
}
关于c# - 算法改进,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20755620/