我这里有一个函数，可以计算数组中唯一整数对的数量，谁的总和是偶数。目前，我已经使用嵌套循环对此进行了编码，但是效率低下，因为嵌套循环会导致O(N²)的时间复杂度。
在此示例中，A表示数组，P和Q表示整数对。 Q应始终大于 P，否则这将导致非唯一整数对(其中 P 和 Q 可以指向数组中的相同值(。
public int GetEvenSumCount(int[] A)
{
// result storage
int result = 0;
// loop through each array element to get P
for (int P = 0; P < A.Length; P++)
{
// loop through each array element to get Q
for (int Q = P + 1; Q < A.Length; Q++)
{
// calculate whether A[P] + A[Q] is even.
if ((A[P] + A[Q]) % 2 == 0)
{
result++;
}
}
}
return result;
}
我现在需要重构它，以便O(N)更糟糕的情况时间复杂度，但我不知道从哪里开始！我知道这将涉及仅使用一个循环，而不是嵌套循环，但我不知道您如何在这方面将A[P]与A[Q]相加。
您可以通过两种方式获得偶数和：
- 添加两个偶数值，如
2 + 4 = 6 - 添加两个奇数值，例如
1 + 3 = 4
相反，将偶数值与奇数值相加将始终是奇数，就像1 + 2 = 3
因此，您可以得到的偶数和总数为：
- 偶数值对的数量
- 另外，奇数值对的数量
n项集合中的对数为：
N = n * (n-1) / 2
完整代码：
static bool IsEven(int i)
{
return i % 2 == 0;
}
static bool IsOdd(int i)
{
return i % 2 != 0;
}
static int GetPairCount(int n)
{
return n * (n- 1) / 2;
}
public static int GetEvenSumCount(int[] A)
{
int evensCount = A.Count(IsEven);
int oddCount = A.Count(IsOdd);
return GetPairCount(evensCount) + GetPairCount(oddCount);
}
如您所见，没有嵌套循环，也不需要实际计算总和。
此实现的复杂性为 O(N(。
仅当两个整数都是奇数或两个整数都是偶数时，两个整数的总和才能是偶数。
扫描阵列，并计算奇数和偶数的数量。假设这些是 N1 和 N2。
The number of pairs = (N1 Choose 2) + (N2 Choose 2).
= N1*(N1-1)/2 + N2*(N2-1)/2
由于两个偶数之和是偶数，两个奇数之和也是偶数(但奇数和偶数的数字是奇数(，我首先将它们分为偶数和奇数：
var grouped = A.GroupBy(x => x % 2 == 0);
现在，每个组中以 n 为元素数的唯一对数为：
(n-1) + (n-2) + … + 1 = n * (n-1) / 2
所以(如果我们在偶数组或奇数组中是独立的(：
return gouped.Sum(x => {var n = x.Count(); return n * (n-1) / 2; });
正如承诺的那样，报告解决方案：
static int GetEvenSumCountFast(int[] A)
{
int[] OddEven = new int[2];
for (int i = 0; i < A.Length; i++)
OddEven[A[i] & 1]++;
return OddEven[0] * (OddEven[0] - 1) / 2 +
OddEven[1] * (OddEven[1] - 1) / 2;
}
好吧，其他人已经解决了它，但无论如何..
另类：
static int GetEvenSumCountFast(int[] A)
{
int odd = 0, even = 0;
for (int i = 0; i < A.Length; i++)
{
odd += A[i] & 1;
even += ~A[i] & 1;
}
return odd * (odd - 1) / 2 +
even * (even - 1) / 2;
}
问题是找到唯一的偶数和...在上述所有解决方案中...在计算奇数和偶数的数量时，他们没有考虑它们的唯一性。例如，如果有两个偶数具有相同的值，例如 4 和另一个偶数 6。将有两个偶数和具有值 10 并且它们是非唯一的
感谢所有为这个问题做出贡献的人，我在这里做了所有的笔记，并制作了一个简洁的函数，它的行为符合预期，并且仍然符合所需的 O(N( 时间复杂度
public int GetEvenSumCount(int[] A)
{
int odd = A.Count(o => o % 2 != 0);
int even = N.Length - odd;
return odd * (odd - 1) / 2 + even * (even - 1) / 2;
}
好吧，我有一个解决方案，即 O(n(。有点。你可以认为这是作弊。大概是吧。
"int" 的范围有限 - +/- 2^31。
我们必须假设可能的数组大小是无限的 - 否则 O (( 表示法没有意义。如果数组大小限制为 2^64 个元素，那么问题总是可以在常量时间 O (1( 中使用 2^128 个操作来解决......
因此，创建数组中包含的所有可能的 2^32 int 值的位图。这需要 O (n( 个步骤。从位图创建一个新数组，并删除所有重复项。该数组最多有最小 (n， 2^32( 个条目。其余的总是可以在 2^64 个操作中完成，即 O(1(。所以总数是 O(n(，但如果 n 在 2^32 左右，则具有一个巨大的常数因子。
如果数组包含字节而不是整数，这实际上将是一个相当快的算法。
现在找到一个有效的算法，这似乎有点困难。