算法练习(70): 最遥远的一对(1.4.17)

本系列博客习题来自《算法(第四版)》，算是本人的读书笔记，如果有人在读这本书的，欢迎大家多多交流。为了方便讨论，本人新建了一个微信群(算法交流)，想要加入的，请添加我的微信号：zhujinhui207407 谢谢。另外，本人的个人博客 http://www.kyson.cn 也在不停的更新中，欢迎一起讨论

知识点

• 最遥远的一对

题目

1.4.17 最遥远的一对（一维）。编写一个程序，给定一个含有 N 个 double 值的数组 a[]，在其中找到一对最遥远的值：两者之差（绝对值）最大的两个数。程序在最坏情况下所需的运行时间应该是线性级别的。

1.4.17 Farthest pair (in one dimension). Write a program that, given an array a[] of N double values, finds a farthest pair : two values whose difference is no smaller than the the difference of any other pair (in absolute value). The running time of your program should be linear in the worst case.

分析

这道题的解法跟上道题差不多，很容易就能解出来。

public class FastestPair {
    public static void fastestPair(double[] x)
    {
        System.out.println("最遥远的两个数为:"+x[0]);
        System.out.println("和:"+x[x.length- 1]);
    }
    
    public static void main(String[] args){
        double[] a = {1,2,3,4,5,888,76,45};
        Arrays.sort(a);
        fastestPair(a);
    }
}

以上代码的地址：FastestPair.java
同样，跟题目的要求不匹配，为何？因为这个算法复杂度是常数级别。因为一旦调用了Arrays.sort(a)后，直接取最大值最小值即可。那怎么符合“线性”复杂度呢，还是要加层循环。

答案

public class FastestPairLinear {
    public static void fastestPairLinear(double[] x)
    {
        double max = Double.MIN_VALUE;
        double min = Double.MAX_VALUE;
        for (int i = 0; i < x.length; i++) {
            if (x[i] >= max) {
                max = x[i];
            }
            if (x[i] < min) {
                min = x[i];
            }
        }
        System.out.println("最遥远的两个数为:"+max);
        System.out.println("和:"+min);
    }
    
    public static void main(String[] args) {
        double[] a = {1,2,3,4,5,888,76,45};
        fastestPairLinear(a);
    }
}

代码索引

FastestPairLinear.java

广告

我的首款个人开发的APP壁纸宝贝上线了，欢迎大家下载。