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

算法(第4版)

知识点

• 成本模型

题目

1.4.8 编写一个程序,计算输入文件中相等的整数对的数量.如果你的第一个程序是平方级别的,请继续思考并以Array.sort()给出一个线性对数级别的解答

1.4.8 Write a program to determine the number pairs of values in an input file that are equal. If your first try is quadratic, think again and use Arrays.sort() to develop a linearithmic solution.

答案

public class TwoSame {
    public static int twoSame(long[] a){
        int cnt = 0;
        for (int i = 0; i < a.length; i++)
        {
            for (int j = i+1 ; j < a.length; j++) 
            {
                if (a[i] == a[j]) {
                    cnt++;
                }
            }
        }
        return cnt;
    }

    public static void main(String[] args) {
        String filePathString = System.getProperty("user.dir");
        String intFileString = filePathString
                + "/src/com/kyson/chapter1/section4/" + "1kints.txt";

        In in = new In(intFileString);
        long[] a = in.readAllLongs();
        
        System.out.println("相同的整数的数量为"+ twoSame(a));
    }
}

这个程序(的算法复杂度)是平方级别的，我们下面做个改动，变成线性级别的

public class TwoSameFast {
    public static int twoSameFast(long[] a){
        int cnt = 0;
        for (int i = 0; i < a.length - 1; i++) 
        {
            if (a[i] == a[i+1]) {
                cnt++;
            }
        }
        return cnt;
    }

    public static void main(String[] args) {
        String filePathString = System.getProperty("user.dir");
        String intFileString = filePathString
                + "/src/com/kyson/chapter1/section4/" + "1kints.txt";

        In in = new In(intFileString);
        long[] a = in.readAllLongs();
        Arrays.sort(a);
        
        System.out.println("相同的整数的数量为" + twoSameFast(a));
    }
}

代码索引

TwoSame.java
TwoSameFast.java

广告

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