审查密码测试 - pair_sum_even_count

Question

作为招聘流程的一部分,我最近对可靠性进行了在线测试.我在1小时内得到了两个简单的问题.对于那些不懂鳕鱼的人来说,它是一个在线编码测试网站,您可以用许多不同语言解决ACM风格问题.

如果您有大约30分钟,请查看http://codility.com/demo/run/

我选择的武器通常是Java.

所以,我遇到的问题之一如下(我会尽量记住,应该截取屏幕截图)

假设您有阵列A [0] = 1 A [1] = - 1 .... A [n] = x

那么找出A [i] + A [j]偶数i <j的最快的方法是什么？

所以,如果我们有{1,2,3,4,5},我们有1 + 3 1 + 5 2 + 4 3 + 5 = 4对甚至是

我写的代码是一些事情

int sum=0;
for(int i=0;i<A.length-1;i++){
 for (int j=i+1;j<A.length;j++){
   if( ((A[i]+A[j])%2) == 0 && i<j) {
       sum++;
    }
  }
}

还有一个限制,如果对的数量大于1e9那么它应该返回-1,但让我们忘记它.

你能为此提出更好的解决方案吗？在正常情况下,元素的数量不会超过1e9.

我想我上面的代码扣除了27分(即它并不完美).Codility对出了什么问题给出了详细的评估,我现在还没有.

Answer 1

两个整数的总和即使并且只有它们是偶数或两者都是奇数.您可以简单地浏览阵列并统计平均值和赔率.从一组大小N组合k个数字的可能性的数量是N!/((N - k)!·k!).你只需要将平均数/赔率为N和2作为k.为此,以上简化为(N·(N-1))/ 2.所有条件i < j都是指定每个组合只计算一次.

Answer 2

您可以在不单独计算每一对的情况下找到总和.

A[i]+A[j]即使A [i]是偶数且A [j]是偶数,也是如此 ; 或者A [i]是奇数,A [j]是奇数.

可以保持最多j的奇数和偶数的运行总数,并根据A [j]是奇数还是偶数加到总和:

int sum = 0;

int odd = 0;
int even = 0;
for(int j = 0; j < A.length; j++) {
    if(A[j] % 2 == 0) {
        sum += even;
        even++;
    } else {
        sum += odd;
        odd++;
    }
}

编辑:

如果你看一下A={1,2,3,4,5},j的每个值都会将对数加上A[j]第二个数.

Even values:
A[j]=2 - sum += 0
A[j]=4 - sum += 1 - [2+4]

Odd values:
A[j]=1 - sum += 0
A[j]=3 - sum += 1 - [1+3]
A[j]=5 - sum += 2 - [1+5, 3+5]

Answer 3

请检查一下

if (A == null || A.length < 2) {
  return 0;
}

int evenNumbersCount = 0;
int oddNumberCount = 0;

for (int aA : A) {
  if (aA % 2 == 0) {
    evenNumbersCount++;
  } else {
    oddNumberCount++;
  }
}

int i = (evenNumbersCount * (evenNumbersCount - 1)) / 2 + (oddNumberCount * (oddNumberCount - 1)) / 2;
return i > 1000000000 ? -1 : i;

如果有人有理解桑特所说的这是另一种解释:只有奇数+奇数甚至+偶数给出偶数.你必须找到有多少偶数和奇数.如果你有它想象这是一个会议的问题.在奇数列表和偶数列表中有多少人偏离对.这是同一个问题,因为在聚会上会有多少人对彼此说.这也是完整图形中的边数.答案是n*(n-1)/ 2,因为有n个人,你必须晃动n-1个人的手并除以2,因为另一个人不能将你的摇动视为不同的一个.正如你在这里有两个单独的"派对",你必须独立计算它们.