1.4.16

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

解答

先将数组从小到大排序,再遍历一遍即可得到差距最小的两个数。

排序算法需要消耗 NlogN,具体见 MSDN:Array.Sort 方法 (Array).aspx)。

代码

using System;

namespace _1._4._16
{
    /*
     * 1.4.16
     * 
     * 最接近一对(一维)。
     * 编写一个程序,给定一个含有 N 个 double 值的数组 a[],
     * 在其中找到一对最接近的值:两者之差(绝对值)最小的两个数。
     * 程序在最坏情况下所需的运行时间应该是线性对数级别的。
     * 
     */
    class Program
    {
        //总运行时间: NlogN + N = NlogN 
        static void Main(string[] args)
        {
            double[] a = new double[5] { 0.1, 0.3, 0.6, 0.8, 0 };
            Array.Sort(a);//Nlog(N) 具体见 https://msdn.microsoft.com/zh-cn/library/6tf1f0bc(v=vs.110).aspx 备注部分
            double minDiff = double.MaxValue;
            double minA = 0;
            double minB = 0;
            for (int i = 0; i < a.Length - 1; ++i)//N
            {
                if (a[i + 1] - a[i] < minDiff)
                {
                    minA = a[i];
                    minB = a[i + 1];
                    minDiff = a[i + 1] - a[i];
                }
            }
            Console.WriteLine($"Min Pair: {minA} {minB}, Min Value: {minDiff}");
        }
    }
}

另请参阅

MSDN-Array.Sort 方法 (Array).aspx)

上一题 下一题