乘积。
示例：
[4, 3, 2, 8] -> [3*2*8, 4*2*8, 4*3*8, 4*3*2] -> [48, 64, 96, 24]
，我给出了以下答案
import java.math.BigInteger;
import java.util.Arrays;
public class ProductOfAnArray {
public static void main(String[] args) {
try {
System.out.println(Arrays.toString(ProductOfAnArray
.calcArray(new int[] { 4, 3, 2, 8 })));
System.out.println(Arrays.toString(ProductOfAnArray
.calcArray(new int[] { 4, 0, 2, 8 })));
System.out.println(Arrays.toString(ProductOfAnArray
.calcArray(new int[] { 4, 0, 2, 0 })));
System.out.println(Arrays.toString(ProductOfAnArray
.calcArray(new int[] {})));
System.out
.println(Arrays.toString(ProductOfAnArray
.calcArray(new int[] { 4, 3, 2, 8, 3, 2, 4, 6, 7,
3, 2, 4 })));
System.out
.println(Arrays.toString(ProductOfAnArray
.calcArray(new int[] { 4, 3, 2, 8, 3, 2, 4, 6, 7,
3, 2, 4 })));
System.out.println(Arrays.toString(ProductOfAnArray
.calcArray(new int[] { 4432432, 23423423, 34234, 23423428,
4324243, 24232, 2342344, 64234234, 4324247,
4234233, 234422, 234244 })));
} catch (Exception e) {
// debug exception here and log.
}
}
/*
* Problem: Given an array of integers, produce an array whose values are
* the product of every other integer excluding the current index.
*
* Assumptions. Input array cannot be modified. input is an integer array
* "produce an array" - type not specified for output array
*
* Logic explanation:
*
* Assume we have array [a,b,c,d] Let multiple be multiple of each element
* in array. Hence multiple = 0 if one of the element is 0; To produce the
* output. Ans at i -> multiple divided by the value at i. if 2 numbers are
* 0 then entire output will be 0 because atleast one 0 will be a multiple
* if 1 number is 0 then every thing else will be 0 except that index whole
* value is to be determined
*
*/
public static BigInteger[] calcArray(final int[] inp) throws Exception {
if (inp == null)
throw new Exception("input is null");
int cnt = 0;
BigInteger multiple = new BigInteger("1");
boolean foundZero = false;
for (int i : inp) {
if (i == 0) {
cnt++;
foundZero = true;
if (cnt < 2)
continue;
else
break;
}
multiple = multiple.multiply(BigInteger.valueOf(i));
}
BigInteger ans[] = new BigInteger[inp.length];
for (int i = 0; i < inp.length; i++) {
if (foundZero) {
if (cnt < 2) {
ans[i] = (inp[i] == 0) ? multiple : new BigInteger("0");
} else {
ans[i] = new BigInteger("0");
}
} else {
ans[i] = multiple.divide(BigInteger.valueOf(inp[i]));
}
}
return ans;
}
}
但是我没有被选中。我想获得我的答案的反馈，看看有什么问题。
#1 楼
可能不是因为代码。也许您不走运，并且有一个更好的候选人或一个在其行业中拥有更多经验的候选人。
如果这不是应用程序（或库函数）的瓶颈，请不要进行过早的优化。天真的解决方案不那么容易理解，开发和维护，因为它并不那么复杂：
n除法是否快于n*n乘法？或多或少相关：YAGNI，简单性-最大化未完成工作量的艺术-从敏捷宣言中必不可少
许多复制粘贴的代码在这里：
public static BigInteger[] calcArray2(int[] input) throws Exception {
if (input == null) {
throw new NullPointerException("input is null");
}
BigInteger result[] = new BigInteger[input.length];
for (int i = 0; i < input.length; i++) {
result[i] = calculateProductExcept(input, i);
}
return result;
}
private static BigInteger calculateProductExcept(int[] input, int exceptIndex) {
BigInteger result = BigInteger.ONE;
for (int i = 0; i < input.length; i++) {
if (i == exceptIndex) {
continue;
}
result = result.multiply(BigInteger.valueOf(input[i]));
}
return result;
}
您可以提取一种方法：
System.out.println(Arrays.toString(ProductOfAnArray
.calcArray(new int[] { 4, 3, 2, 8 })));
System.out.println(Arrays.toString(ProductOfAnArray
.calcArray(new int[] { 4, 0, 2, 8 })));
即使在练习中，吞咽异常也不是一个好习惯：
private static void printProductOfArray(int... input) throws Exception {
System.out.println(Arrays.toString(ProductOfAnArray.calcArray(input)));
}
如果有的话抛出一个异常，您将错过它。您可以修改
main方法以引发异常并改为删除try-catch块：} catch (Exception e) {
// debug exception here and log.
}
（实用程序员：Andrew Hunt和David Thomas从《 Journeyman到Master》 ：死程序无话可说。）
您可以在此处引发更具体的异常，例如
IllegalArgumentException或NullPointerException：public static void main(String[] args) throws Exception {
用空输入数组调用该方法是一个编程错误，因此此处最好使用未经检查的异常。 （这将使
throw Exception上的main不必要。）我想
result（作为变量名）在这里会更容易理解：if (inp == null)
throw new Exception("input is null");
我也要避免缩写。我发现它们破坏了自动完成功能。 （当您在Eclipse中键入
co并按Ctrl + Space时，它什么也没找到，但可以找到count。）此外，它们还需要进行心理映射（读取器/维护器每次都必须对其进行解码。另请参见：Robert C. Martin的“清洁代码”，使用意图公开名称，第18页；使用可发音名称，p21；避免心理映射，p25
我已将此变量重命名为
fullProduct或更能表达其目的的描述性名称：BigInteger ans[] = new BigInteger[inp.length];
#2 楼
对于初学者来说，您有非常奇怪的换行符：System.out
.println(Arrays.toString(ProductOfAnArray
.calcArray(new int[] { 4, 3, 2, 8, 3, 2, 4, 6, 7,
3, 2, 4 })));
这不是布局，而是混淆！处理长方法链时，最好在每次方法调用之前先中断：
someObject
.thisIs()
.aFluid()
.interface();
，但这不是这种情况，并且这种布局不会增加可读性。相反，请中断参数列表的开头括号：
System.out.println(
Arrays.toString(ProductOfAnArray.calcArray(new int[] {
4, 3, 2, 8, 3, 2, 4, 6, 7, 3, 2, 4
}))
);
或类似的东西。请注意，使用varargs声明函数时，您可能将其写为
System.out.println(
Arrays.toString(ProductOfAnArray.calcArray(
4, 3, 2, 8, 3, 2, 4, 6, 7, 3, 2, 4
))
);
（即，没有显式数组）：
calcArray(int... inp)。下一个问题是为什么要返回数组–
List<BigInteger>会更灵活–数组在现代Java中几乎没有用（varargs的使用暗示着数组，高性能代码可能需要它们。但是在所有其他情况下，它们也是如此不灵活-例如数组和泛型不能一起使用）。但是为什么
BigInteger？是的，您不想溢出，但是我们可以假设您的面试官会对int感到满意。如果要允许更大的数字，第一步是long。 Big Integer确实使用起来很尴尬，而且性能可能不如原生类型，因此我会尽可能避免使用它们。calcArray中的代码不必要地聪明。让我们看一下这个循环：for (int i : inp) {
if (i == 0) {
cnt++;
foundZero = true;
if (cnt < 2)
continue;
else
break;
}
multiple = multiple.multiply(BigInteger.valueOf(i));
}
请注意，
foundZero等效于cnt > 0，并且您没有在内部if/else的主体周围使用花括号。您的continue相当混乱，下面的代码更好地表达了控制流程：for (int i : inp) {
if (i != 0) {
multiple = multiple.multiply(BigInteger.valueOf(i));
}
else {
cnt++;
if (cnt >= 2) {
break;
}
}
}
下一个循环中的此条件也太复杂了，可以简化为
if (cnt < 2 && inp[i] == 0) {
ans[i] = multiple;
} else {
ans[i] = new BigInteger("0");
}
应用这些批评时，可能起作用的最简单的方法可能是：
public static List<Long> specialProduct(int... numbers) {
long product = 1;
int zeroesCount = 0;
for (int n : numbers) {
if (n != 0) {
product *= n;
}
else {
zeroesCount++;
}
}
List<Long> output = new ArrayList<>(numbers.length);
switch (zeroesCount) {
case 0:
// with no zeroes, we don't have to perform any checks
for (int n : numbers) {
output.add(product / n);
}
break;
case 1:
// with one zero, the all others will become zero too
for (int n : numbers) {
if (n == 0) {
output.add(product);
}
else {
output.add(0L);
}
}
break;
default:
// two or more zeroes make everything zero
for (int i = 0; i < numbers.length; i++) {
output.add(0L);
}
break;
}
return output;
}
哦，命名！人声变得如此珍贵，以至于我们必须写
cnt而不是count吗？如果您实际上可以写像ans这样的长字，我们必须写answer而不是multiple吗？ Q4312079q到底是什么呢？您的代码不错，但它不是很好，并且肯定可以写得更好。下次，也许:)
评论
\ $ \ begingroup \ $
我同意零的特殊处理是不必要的，我喜欢先计算总乘积然后考虑当前输入的总想法，但是如果简化的解对所有元素都产生零，则如果对零的至少一个为零。输入，例如[0,1,2,3]-> [0,0,0,0]，但正确的结果应为[6,0,0,0]。
\ $ \ endgroup \ $
–西蒙·莱曼（Simon Lehmann）
2014年3月27日15:25
\ $ \ begingroup \ $
也许我误解了最初的问题，但是在阅读了OP解决方案之后，我认为它包含相同的错误，这很可能是拒绝它的原因。
\ $ \ endgroup \ $
–西蒙·莱曼（Simon Lehmann）
2014年3月27日15:31
\ $ \ begingroup \ $
@SimonLehmann您可能应该将其发布为答案：因为这可能是拒绝解决方案的最重要原因，即“输出不正确”。
\ $ \ endgroup \ $
– ChristW
2014年3月27日15:41
\ $ \ begingroup \ $
@ChrisW：OP的代码返回[0,1,2,3]的[6,0,0,0]。
\ $ \ endgroup \ $
–palacsint
2014年3月27日15:47
\ $ \ begingroup \ $
好吧，好吧，我应该花更多的时间阅读该代码（并尝试一下）。 OP的程序没有此错误，因为它在循环中使用“继续”，该循环在遇到零时就计算总乘积。现在我想，它被拒绝的真正原因可能是它太复杂了...
\ $ \ endgroup \ $
–西蒙·莱曼（Simon Lehmann）
2014年3月27日15:48
#3 楼
rolfl的答案叫“嵌套循环的原始O（n2）解决方案”可能会更好：它的速度较慢，但对于较小/很少使用的数组无关紧要
如果您的解决方案使用的是
int而不是BigInteger，那么幼稚的解决方案将处理更多/更大的输入数字，这是一个小小的奖励（并且，决定使用BigInteger，因为您尚未弄清输入可能有多大的性能的后果）更明显（从问题到解决方案的映射）并且更易于阅读（因为它更明显），这可能比针对速度进行优化更重要
电话采访中，您是否提出过以下问题：
数组是否很长？
我应该针对最大速度，最小内存或最大可读性进行优化吗？
/>
提问可能是面试过程的一部分：“考生是否会在编码之前提出问题以澄清歧义？”
我不容易通过检查来验证您的
calcArray是否正确。也许我不像你那么聪明。main中的代码有很多重复的System.out.println(Arrays.toString(ProductOfAnArray.calcArray语句。相反，最好有输入数组的集合，您可以对其进行迭代（依次将每个数组传递给calcArray）。
如果测试数据是输入数组和期望输出的集合，则更好，以便代码可以断言是否为实际输出符合预期的输出。
评论
\ $ \ begingroup \ $
同意您所说的所有内容，但“在更广泛的条件下正确（不太可能发生溢出）很重要，这很重要”……这意味着X次错是不好的，但X-1次错了还行吧...
\ $ \ endgroup \ $
–rolfl
2014年3月27日15:12
\ $ \ begingroup \ $
+1提出要求的问题非常重要！它证明您正在尝试了解自己在做什么，并且不理会细节。
\ $ \ endgroup \ $
–马克·安德烈（Marc-Andre）
2014年3月27日15:34
\ $ \ begingroup \ $
@ChrisW我确实问过面试官那些问题。他说你可以承担任何责任。他只是想让我开始写代码，而不说话。
\ $ \ endgroup \ $
–脚步
2014年3月27日16:20
\ $ \ begingroup \ $
可以构建一个O（n）解决方案，该解决方案与O（n ^ 2）解决方案一样处理大数，只是OP没有做到这一点。计算出out [0]作为乘积（in [1..n]），然后计算出out [n] = out [n-1] / in [n] * in [n-1]。这样，您将永远不会拥有整个阵列的产品，这是OP解决方案中主要的性能问题。
\ $ \ endgroup \ $
–红色警报
2014年3月27日21:15
\ $ \ begingroup \ $
@RedAlert当输入中除第一个位置外的其他任何位置上正好有一个零，例如in = [1,0,2,3]-> out [0] = 0 * 2 * 3 = 0，out [1] = 0/0 * 1 = NaN，out [2] = NaN / 2 * 0 = NaN，out [3] = NaN / 3 * 2 = NaN。即使检查是否除以零，您也会错误地设置[1] = 0！实际上，您持有整个数组的乘积，但第一个元素有点奇怪，特别是作为“性能”参数时，要说“您永远不会持有整个数组的乘积”。
\ $ \ endgroup \ $
–西蒙·莱曼（Simon Lehmann）
2014年3月28日在22:29
#4 楼
正如@rolfl所说，您的代码对我来说也很好。我只是想添加一些关于您的代码的非常小的注释。样式
if (inp == null)
throw new Exception("input is null");
格式化
if的这种特殊方式可能被视为问题。有时不将括号用于单行有时会被视为不好。这实际上是次要点，不应影响求职面试的结果，但是如果他们非常狂热，则可能会产生影响。 测试
您的主要工具对我来说就像一堆测试。我不知道您生成代码的时间，但确实知道测试对许多公司来说都很重要。您可以将这些自制的“测试”转换为一整套JUnit测试。我认为这可以使您胜过其他候选人。这将有助于显示您对需求的了解并预测代码的行为方式。它可以帮助您了解您为什么要像以前那样做某些事情。
常量
其他次要点，在可用时应使用常量。
BigInteger multiple = new BigInteger("1");
new BigInteger("0");
应该是
BigInteger multiple = BigInteger.ONE;
BigInteger.ZERO;
/>您的代码中的
new将会更少，因此如果该函数被大量调用会有所帮助！#5 楼
老实说.....看起来不错。这几乎是我要做的。 O（n）比嵌套循环的朴素O（n2）解决方案更聪明，它可以通过BigInteger很好地管理溢出...这很好。可能期望使用
int[]返回类型，并且假定不会发生溢出。 br /> 您知道这有溢出的风险，并且根据实际需求，如果需要，我会使用
int[]对其进行编码。仍然，我想在那里是您没有找到工作的其他原因...。不是此代码...。而且，如果这是代码，那么您可能还是不想在那里工作；-)
祝一切顺利。
#6 楼
这样的东西怎么办？import java.util.Arrays;
public class ArrayCalc {
public static void main(String[] args){
Integer[] exparray = {2,3,4};
Integer[] resultarray = new Integer[exparray.length];
for (int i = 0; i< exparray.length; i++){
if(!exparray[i].equals(0)){
Integer result = 1;
for (int j = 0; j<exparray.length; j++)
result = result * exparray[j];
result = result/exparray[i];
resultarray[i] = result;
}
}
System.out.println(Arrays.toString(resultarray));
}
}
评论
\ $ \ begingroup \ $
请您解释一下为什么要这样做的原因吗？
\ $ \ endgroup \ $
–马拉奇♦
2014年3月27日21:16
\ $ \ begingroup \ $
OP指出：我想获得我的答案的反馈，看看有什么问题。这绝不解决OP的代码，而仅仅是代码转储。请查看OP的代码（您甚至可以解释如何获得更好的解决方案），否则此答案可能会被删除。
\ $ \ endgroup \ $
– Jamal♦
2014年3月27日在21:58
评论
感谢大家的反馈。下次编写任何代码时，我都会考虑所有这些。这是算法本身的提示：索引i上的结果是所有元素/ inp [i]
的乘积
似乎这个问题太容易了，如果他们没有时间去采访至少做得很好的每个人，那么最好做些更难的事情，并获得一些肉质的差异。
当系统询问您通过电话进行采访并为他们提供代码时，这并不是他们想要的。他们想让您用英语解释您的工作。
不好的算法，更好的方法是将数组中的所有数字相乘，然后将当前索引中的数字除以计算结果。这是一个算法问题，我认为面试官不会真正关注您的编码风格。