1.4.12

上次更新:2019-04-17
发现了题解错误/代码缺陷/排版问题?请点这里:如何:提交反馈

解答

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

设 i, j 分别为两个数组的下标。
如果 a[i] == a[j],i 和 j 都向后移动一位。
如果 a[i] != a[j],比较小的那个向后移动一位。
循环直到某个数组遍历完毕。

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

代码

using System;

namespace _1._4._12
{
    /*
     * 1.4.12
     * 
     * 编写一个程序,有序打印给定的两个有序数组(含有 N 个 int 值) 中的所有公共元素,
     * 程序在最坏情况下所需的运行时间应该和 N 成正比。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            int[] a = new int[4] { 2, 3, 4, 10 };
            int[] b = new int[6] { 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++;
                }
            }

        }
    }
}
上一题 下一题