如何比较时间复杂度小于 O(n^2) 的两个数组中的每个元素

Question

假设我们有两个数组 A[n] 和 b[n]，目标是将 A 中的每个元素与 B 中的元素进行比较。然后 return 一个记录数字的列表 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].

如果能提供一些伪代码最好

谢谢。

Answer 1

两个列表都需要按升序排序才能工作。

分类成本O(log n)。而大 O 算术意味着做两次仍然是 O(n log n)。我将假设它们已经排序。下面的剩余工作不会影响 big-O 成本。

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

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

在那之后，result 中从 indexA 开始的所有剩余项都比 B 中的所有项都大，因此将其余项设置为 B.Length.

在发布我的原始答案 2 年后编辑，添加： 实际 C# 代码以反映上述伪代码。我相信下面的代码是 O(n)，与首先对数组进行排序的成本相比，这可以忽略不计（在 big-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));

Answer 2

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

算法

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).

希望对您有所帮助！

如何比较时间复杂度小于 O(n^2) 的两个数组中的每个元素

How to compare each element in two arrays with time complexity less than O(n^2)

algorithm

divide-and-conquer

算法