您可以在Codility网站以及此处看到问题，我的代码和分数。
问题定义
写一个函数：
/>
class Solution { public int solution(int[] A); }
给定零索引数组A，则返回缺少元素的值。
例如，给定数组A使得：
A[0] = 2
A[1] = 3
A[2] = 1
A[3] = 5
该函数应返回4，因为它是缺少的元素。假定：
N是[0..100,000]范围内的整数；
A的元素都是截然不同的；
数组A的每个元素都是在[1 ..（N + 1）]范围内的整数。复杂度：
预期的最坏情况下的时间复杂度为O（ N）;
预期的最坏情况下的空间复杂度是O（1），超出了输入存储（不计算输入参数所需的存储）。
输入数组的元素可以修改。
解决方案
这是我作为答案编写的代码：
public class Solution {
public int solution(int[] A) {
int N = A.length + 1;
int total = N * (N + 1) / 2;
for (int i : A) {
total -= i;
}
return total;
}
}
#1 楼
@chillworld认为该问题与导致性能测试中出现问题的int溢出有关，这是正确的。对此的更准确解决方案是使用
long设置得分，而不是int。public class Solution {
public int solution(int[] A) {
long N = A.length + 1;
long total = N * (N + 1) / 2;
for (int i : A) {
total -= i;
}
return (int)total;
}
}
对于您的代码，我理解为什么您要使用具有诸如
N和A之类的名称的变量，因为这些是问题中使用的变量名称。那些变量名称不符合标准Java虽然命名约定。它们应该是有意义的名称，并以小写字母开头，例如
sum和data。我下面的代码仍然使用
N的事实并不表示可以。...。 ，而不是我的工作... 更新
有时，Java中的性能技巧可能是PITA。
只要有可能，就将变量声明为final
将方法声明为final
将变量和for-loop变量声明为final（如果使用增强型for语义）。
加法可能会或可能不会快于减法。
/>
使用此代码：
class Solution {
public final int solution(final int[] data) {
final long N = data.length + 1;
final long total = (N * (N + 1)) / 2;
long sum = 0L;
for (final int i : data) {
sum += i;
}
return (int)(total - sum);
}
}
得分100％
更新2最终不是问题：
public int solution(int[] data) {
long N = data.length + 1;
long total = (N * (N + 1)) / 2;
long sum = 0L;
for (int i : data) {
sum += i;
}
return (int)(total - sum);
}
也得分100 ％
评论
\ $ \ begingroup \ $
相信我，我尝试了给出相同结果的解决方案:)。但是变量名称不会影响性能吗？
\ $ \ endgroup \ $
–quartaela
2014-4-17 13:27
\ $ \ begingroup \ $
@quartaela-更新了100％解决方案的答案。
\ $ \ endgroup \ $
–rolfl
2014年4月17日下午13:37
\ $ \ begingroup \ $
非常感谢，但我不明白。如何将变量定义为最终将性能从60提高到100？
\ $ \ endgroup \ $
–quartaela
2014年4月17日下午13:41
\ $ \ begingroup \ $
@quartaela-我非常相信您的代码仅通过基于长期的算术就可以通过....性能测试失败了，但并不慢。上面的代码仅给出了一种在所有情况下都适用的解决方案，而不仅仅是较小的数据集。我将使用相同的代码进行另一个测试，但最终的测试结果不同，然后看看会发生什么。
\ $ \ endgroup \ $
–rolfl
2014年4月17日下午13:44
\ $ \ begingroup \ $
令人印象深刻，尽管它对我的Java看法并没有太大帮助：\
\ $ \ endgroup \ $
– konijn
2014年4月17日下午13:45
#2 楼
您还可以使用Java 8IntStream API来对数组求和并最小化代码：public int solution(int[] A) {
long N = A.length + 1;
return (int) (((N*(N+1))/2)-IntStream.of(A).sum());
}
这将得分100％。
#3 楼
从站点开始：WRONG ANSWER
got -2147483647 expected 1
所以int溢出是因为您对所有内容都进行了计数。
解决该问题的方法：
public int solution(int[] A) {
int previous = 0;
if (A.length != 0) {
Arrays.sort(A);
for (int i : A) {
if (++previous != i) {
return previous;
}
}
}
return ++previous;
}
结果请参见此处：https://codility.com/demo/results/demoS45RNV-37J/
评论
\ $ \ begingroup \ $
Arrays.sort通常是O（n log n）操作，因此它可能无法通过可伸缩性测试。
\ $ \ endgroup \ $
–rolfl
2014年4月17日下午13:23
\ $ \ begingroup \ $
我错过了要求中的某些内容吗？当我发送int [] A = {26,23,21,24,22};的输入时，使用您的方法没有得到所需的结果。可能是我在要求中缺少某些内容，因此请澄清一下。
\ $ \ endgroup \ $
–user47764
2014年7月7日在3:41
\ $ \ begingroup \ $
@KayAshton这将不起作用，因为前提是您必须从1开始（如果缺少1，则从2开始）。同样，当您有int [] A = {25,23,21,24,22};时，也无法获得确切的结果。因为可能是20或26。
\ $ \ endgroup \ $
– chillworld
2014年7月7日10:33
\ $ \ begingroup \ $
这个答案是不正确的，因为仅仅需要一个以N为界的解决方案。
\ $ \ endgroup \ $
–克里斯托·克里斯托夫（Christo S. Christov）
15年3月18日在20:22
\ $ \ begingroup \ $
@CodingChief不正确和未优化之间有区别。该代码适用于每种情况，但实际上rolfl他的代码得到了更优化，这也是他的答案被接受为正确答案的原因。
\ $ \ endgroup \ $
– chillworld
15年3月19日在6:40
评论
难道不为您提供有关此的更多详细信息吗？实例的测试用例类型我分享了一个链接，该链接仅提供了简短的测试报告。他们没有分享详细的报告。
好的，我没看到。因此，这实际上是一个正确性问题，而不是性能问题。
我很困惑。人们从哪里获得总计的公式？显然，结果是所有数组元素加上缺失元素的总和，因为这就是我们如何对待它以获得正确答案。但是，我们如何得出该公式？
@KairisCharm这是算术级数公式。每个人都讨论简单的部分（实现）并认为数学是理所当然的，这对解决方案来说是最具挑战性的。此测试不是针对软件工程的测试，而是对代数的测试。en.wikipedia.org/wiki/Arithmetic_progression