我们如何优化最小绝对差之和，从 O(nlogn) 到 O(n)

Question

我想知道我们如何优化这个问题，我们有 2 个数组，我们需要找到每个元素之间的最小差异并返回其总和

[3,4,1]  [2,3,4] 

基本的事情是对数组进行排序然后

+(arr1[i] - arr2[i])

但是，如果我们创建一个像

int arr[10000000];

这样非常大的 2 个数组，并将每个元素的出现存储在大元素的索引上，那么最终结果将像

[0,1,0,3,4,0,0,0...]

一样，毫无疑问，这将是 O(n) 但会它比排序算法更快？考虑到我们正在迭代整个 10^5 大小的数组，即使原始数组大小仅为 3/4 左右？

会更快还是更慢？它能给你在 leetcode 类型平台上提供更好的结果吗？或者也许给我来自 leetcode 的确切问题，我想我会自己测试一下。

确切的问题 -

给定两个整数数组，arr1 和 arr2。您的任务是找到两个数组中每个对应元素之间的最小差异，并返回这些最小差异的总和。两个数组的长度相同。

Array 1 - [3,2,1] 
Array 2 - [1,2,3] 
Output - 0 
Explanation - |1-1| + |2-2| + |3-3|= 0```
                                    

Answer 1

未优化的算法将循环第一个数组 (O(n))，对于每个元素，计算有多少个较小的元素和多少个较大的元素 (O(n))，然后在第二个数组中找到相应的元素，通过循环它（O(n)），并为每个元素找出是否匹配（O(n)），即 O(n^4)。

如果对两者都进行排序，则为 O(nlogn) * 2，即排序的 O(nlogn)。然后循环索引并对差异求和 (O(n))，这样就得到了

O(n^4) 与 O(n + nlogn)

即：

O(n^4) 与 O((n + 1)logn)

即：

O(n^4) 与 O(nlogn)

因此，就步骤数而言，进行排序是更优化的。

但仍然存在一些担忧。首先，将

writes 排序到内存中，在数组的整个区域中，这比仅仅读取的成本要高得多。其次，修改数组，这在较大任务的上下文中可能是一个很大的禁忌，提示您将两个数组“复制”到临时数组中，以便可以在不损坏原始数组的情况下对它们进行排序，这会增加时间消耗和内存消耗也是如此，这将比不排序的方法更早达到内存限制。 因此，一如既往，您需要自己决定您最关心的是什么，答案将帮助您选择解决方案。