为使此方法有效,两个列表都需要按升序排序。
排序的成本为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)
。
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));