面试-在数组中寻找偶数和对

Question

给定一个数组，您将如何返回和为偶数的对的数量？

例如：

a[] = { 2 , -6 , 1, 3, 5 }

在此数组中，与偶数和配对的编号为(2，-6)，(1,3)，(1,5)，(3,5)

函数应该返回4，因为有4对，如果没有，则返回-1。

预期时间复杂度- O(N)最坏情况预期空间复杂度- O(N)最坏情况

方法1:暴力破解

Start with the first number
  Start with second number
      assign the sum to a temp variable
      check if the temp is even
          If it is increment evenPair count
      else
          increment the second index

这里的时间复杂度为O(N2)

Answer 1

int odd = 0, even = 0;
for (int i = 0; i < n; i++) {
    if (a[i] % 2 == 0) {
        even++;
    } else {
        odd++;
    }
}
int answer = (odd * (odd - 1) + even * (even - 1)) / 2;

Answer 2

如果要使用标准算法，则代码可能如下所示

#include <iostream>
#include <utility>
#include <numeric>
#include <iterator>

int main() 
{
    int a[] = { 2 , -6 , 1, 3, 5 };

    typedef size_t Odd, Even;
    auto p = std::accumulate( std::begin( a ), std::end( a ), 
                              std::pair<Odd, Even>( 0, 0 ),
                              []( std::pair<Odd, Even> &acc, int x )
                              {
                                return x & 1 ? ++acc.first : ++acc.second, acc;
                              } );

    std::cout << "There are " 
              << ( p.first * ( p.first - 1 ) + p.second * ( p.second - 1 ) ) / 2
              << " even sums" << std::endl;

    return 0;
}

输出为

There are 4 even sums

考虑到n! / ( 2! * ( n - 2 )! )等同于( n - 1 ) * n / 2

使用标准算法的优点是您可以使用序列的任何子范围。您还可以使用标准流输入，因为std::accumulate使用输入迭代器。

此外，如果在赋值的描述中写道，如果数组的元素之间没有偶数和，则函数应返回0而不是-1，这会更好。

在面试中展示这段代码并不丢人，尽管我建议千万不要在面试中做任何作业。面试不是考试。

Answer 3

如果a和b是偶数，则a+b是偶数。

如果它们是奇数，a+b也是偶数。

如果一个是奇数，一个是偶数，则a+b是奇数。

这意味着我们不需要执行任何加法，我们只需要知道每种类型的数字有多少。

找出这一点需要线性时间。

如果有k个数字，则有k-1对包含第一个数字，k-2包含第二个数字，依此类推。

使用熟悉的求和公式sum(1 .. n) = (n * (n + 1)) / 2，

让

ne = number of even numbers
no = number of odd numbers

然后,

number of pairs = (ne-1) * ne / 2 + (no-1) * no / 2 
                = ((ne-1)*ne + (no-1)*no) / 2

该计算在固定时间内运行，因此时间复杂度仍然是线性的。

我们只需要一个恒定的额外空间，这比要求的要好。

可能需要考虑的后续面试问题：

如果出现以下情况，复杂性(在时间和空间上)会发生什么：

• 重复项只计算一次，即{1,1,1,2}只有两个这样的对-
• 我们忽略顺序，即(1,2)和(2,1)是“相同”对-