如何在时间复杂度低于O(n^2)的情况下比较两个数组中的每个元素？

Question

假设我们有两个数组A[n]和B[n]，目标是比较A中的每个元素与B中的元素。然后返回一个列表result[n]，记录A中每个大于B中元素的元素的数量。

例如，

A = [38, 24, 43, 3]，B = [9, 82, 10, 11]

由于38大于9、10和11，所以result[0]为3。然后结果是[3, 3, 3, 0]。

如果您能提供一些伪代码，那就太好了。

谢谢。

- Zack

---

如果您能提供一些想法，那将是非常棒的。 - dehasi

如果它们都被排序了，那么遍历列表并在B中找到大于A中每个元素的元素的索引将变得非常容易，时间复杂度为O(n)。 - MyiEye

你能提供一些你遇到这个问题的链接吗？比如leetcode、geeksforgeeks、hackerrank等。 - Jaideep Singh

Answer 1

根据问题中给出的数组A和B的长度n，您可以以O(nlogn)复杂度执行上述算法。

算法

1. Sort both the arrays A and B, this will take O(nlogn) time complexity.
2. Take two pointers i and j, initialize both of them to 0. we will use i for array A and j for B.
3. Create a result array res of size n.
4. Start a while loop 
   while(i<n && j<n) {
     if(A[i] > B[j]) {
       j++;
     } else {
       res[i] = j+1;
       i++;
     }
   }
5. while(i<n) {
     res[i] = n;
   }
   This step is for the case where all elements in A are bigger than all elements in B.

最终，您将拥有准备好答案的res数组。

总时间复杂度为O(nlogn)。

希望这可以帮助您！

- zenwraight

---

这太棒了！！非常感谢。顺便说一下，在第4步循环的最坏运行时间应该是O(n)，对吧？ - Zack

@Zack，这会给出错误的值，如果A中的任何值都比B中的所有值都大，则会得到不完整的结果。请尝试我的答案。 - Richardissimo

即使经过编辑，它仍然不正确，这让人感到沮丧，因为它被标记为被接受的答案并得到了赞同，而我的答案是正确的并且没有得到认可。 - Richardissimo

@Richardissimo，我错过了什么情况，我们可以改进答案。 - zenwraight

@zenwraight 当i=n-1且j=n-1时，您的res列表将不会更新。因此，您需要将line algo的第6和第7步放在“else if”中，而唯一的“if”将包含条件（i==n-1 and j==n-1 and A[i]>B[j]）。然后执行j+=1并将其附加到列表。另外，您的else部分将无法正常工作，它会使j比应该的大1。因此，请保持res[i]=j，而不是res[i]=j+1。 - Jaideep Singh

Answer 2

为使此方法有效，两个列表都需要按升序排序。

排序的成本为O(log n)。而大O算法意味着进行两次排序仍然是O(n log n)。我假设它们已经被排序了。下面剩余的工作不会影响大O成本。

在B数组中有一个名为indexB的索引，值为零（我的伪代码将使用从零开始的索引）。对于A也有一个名为indexA的索引，起始值也为零。

indexA=0
For each indexB from 0 to B.Length-1
    While indexA < A.Length and the value at `A[indexA]` is less than or equal to the value at `B[indexB]`
        Set the `result[indexA]` to be `indexB`
        Increment `indexA`
    Endwhile
Endfor

接下来，从indexA开始的result中剩余的所有项都比B中的所有项都大，因此将它们的值设置为B.Length。

---

在发布原始答案两年后进行编辑，添加以下内容：实际的C#代码以反映上述伪代码。我相信下面的代码是O(n)，这在大O术语中是可以忽略不计的，与首次排序数组的成本相比，因此总成本仍然为O(n log n)。

            // Note: I am simulating pre-sorted arrays, which costs "O(n log n)"...
            // The reason for adding this sample code is to help clarify the cost of the
            // remaining work (after the sorts) by showing real code, to avoid any
            // ambiguity from the pseudocode, even though that's what the OP asked for
            var A = new[] { 3, 24, 38, 43 };
            var B = new[] { 9, 10, 11, 82 };
            var result = new int[4];

            int indexA = 0;
            for (int indexB = 0; indexB < B.Length; indexB++)
            {
                while (indexA < A.Length && A[indexA] <= B[indexB])
                {
                    result[indexA] = indexB;
                    indexA++;
                }
            }

            while (indexA < A.Length)
            {
                result[indexA] = B.Length;
                indexA++;
            }

            Console.WriteLine(string.Join(", ", result));

- Richardissimo

---

这里我可以看到一个嵌套的 while 循环在 foreach 循环内部。复杂度将会是 O(n^2)。 - jithil

@jithil 它没有在每个循环中迭代所有项目。你需要实际查看逻辑。尝试跟踪indexA发生了什么。 - Richardissimo

但是，在大O符号表示法中，O(n*(n/2)) => O(n^2) ，因为常数将被排除。 - jithil

@jithil，你从哪里得到了n/2，为什么要将其乘以n？“for”循环是n，其中的“while”循环是独立于包含它的for循环的，并且也是n。因此，它将执行n+n次工作，这是O(2*n)，相当于O(n)。 - Richardissimo

@jithil 请查看代码并尝试运行它。您可以添加自己的断点或消息。最坏的情况是 n+n。事实上，这总是它将执行的次数。对于4个项目，它会做8个工作，而不是16个。如果A和B中每个都有1000个项目，则会执行2000个工作，而不是一百万个。 - Richardissimo