java - 使用大输入集/边缘情况查找数组中对数的原始算法似乎失败

Question

TLDR：谁能解释一下为什么我建议的算法不适用于大型未排序的数据集？

这是一个足够简单的问题：查找数组中对象对的数量，例如

{1,2,3,4,5,3} 其中整数表示项目类型，预期输出是找到 1 对。

我下面的算法似乎能够解决小数据集：

static int findPairs(int n, int[] ar) {
    int pairCount = 0;
    int itemCount = 1;
    for (int i = 0; i <= n - 1; i++) {
        for (int j = i + 1; j < n && ar[j] != 0; j++) {
            if (ar[i] == ar[j]) {
                itemCount ++;
                if (itemCount % 2 == 0) {
                    pairCount ++;
                }
                ar[j] = 0;
            }
            if (j == n - 1) {
                // reset counter
                itemCount = 1;
            }
        }
    }

    return pairCount;
}

如果我输入一个非常小的数据集，例如

10 20 20 10 10 30 50 10 20

算法输出就好了。

然而，我开始对算法进行压力测试，我使用了一个包含 100 个项目的非常大、复杂的数据集：

int[] ar = {50, 49, 38, 49, 78, 36, 25, 96, 10, 67, 78, 58, 98, 8, 53, 1, 4, 7, 29, 6, 59, 93, 74, 3, 67, 47, 12, 85, 84, 40, 81, 85, 89, 70, 33, 66, 6, 9, 13, 67, 75, 42, 24, 73, 49, 28, 25, 5, 86, 53, 10, 44, 45, 35, 47, 11, 81, 10, 47, 16, 49, 79, 52, 89, 100, 36, 6, 57, 96, 18, 23, 71, 11, 99, 95, 12, 78, 19, 16, 64, 23, 77, 7, 19, 11, 5, 81, 43, 14, 27, 11, 63, 57, 62, 3, 56, 50, 9, 13, 45};

而且代码似乎失败了。预期的答案是 28 对，但这个算法输出 6 对。

现在，这是在未排序数组中查找对的蛮力 (O(n^2)) 尝试。

所以我决定先对数组进行排序，然后调用相同的方法findPairs，奇怪的是，现在它可以工作了：

Given Array
50 49 38 49 78 36 25 96 10 67 78 58 98 8 53 1 4 7 29 6 59 93 74 3 67 47 12 85 84 40 81 85 89 70 33 66 6 9 13 67 75 42 24 73 49 28 25 5 86 53 10 44 45 35 47 11 81 10 47 16 49 79 52 89 100 36 6 57 96 18 23 71 11 99 95 12 78 19 16 64 23 77 7 19 11 5 81 43 14 27 11 63 57 62 3 56 50 9 13 45 

Sorted array
1 3 3 4 5 5 6 6 6 7 7 8 9 9 10 10 10 11 11 11 11 12 12 13 13 14 16 16 18 19 19 23 23 24 25 25 27 28 29 33 35 36 36 38 40 42 43 44 45 45 47 47 47 49 49 49 49 50 50 52 53 53 56 57 57 58 59 62 63 64 66 67 67 67 70 71 73 74 75 77 78 78 78 79 81 81 81 84 85 85 86 89 89 93 95 96 96 98 99 100 
Number of pairs = 28 

Q1：谁能解释一下为什么我建议的算法不适用于大型未排序的数据集？我似乎无法理解为什么它不会。

额外问题加进度更新如下

所以，为了尝试解决这个问题，我的思路是：

1) Doing a mergeSort which is much more efficient than traditional sort
2) Iterate through the now sorted array once to count all the pairs 

我已经完成并且确实有效（如果您想查看代码，请告诉我）。

Q2：但是，单独的 MergeSorting 的代码很长（两个 longass 方法），如果可能的话，我想只实现一个方法调用，并尽可能快地保持时间复杂度，欢迎任何建议！

谢谢！

标签： javaarraysalgorithmperformancesorting