1.4.12

1.4.12 #

解答 #

由于两个数组都是有序的，可以同时进行比较。

设 i, j 分别为两个数组的下标。

如果 a[i] == a[j]，i 和 j 都向后移动一位。

如果 a[i] != a[j]，比较小的那个向后移动一位。

循环直到某个数组遍历完毕。

这样最后的时间复杂度 ~2N

代码 #

var a = new[] { 2, 3, 4, 10 };
var b = new[] { 1, 3, 3, 5, 10, 11 };

// 2N 次数组访问，数组 a 和数组 b 各遍历一遍
for (int i = 0, j = 0; i < a.Length && j < b.Length;)
{
    if (a[i] < b[j])
    {
        i++;
    }
    else if (a[i] > b[j])
    {
        j++;
    }
    else
    {
        Console.WriteLine($"Common Element:{a[i]}, First index: (a[{i}], b[{j}])");
        i++;
        j++;
    }
}