《算法第四版》课后练习题1.1.39答案

习题1.1.39

随机匹配。编写一个使用 BinarySearch 的程序，它从命令行接受一个整型参数 T，并会分别针对N  = 10的三次方 、10的四次方 、10的五次方 和10的六次方 将以下实验运行 T 遍：生成两个大小为 N 的随机 6 位正整数数组并找出同时存在于两个数组中的整数的数量。打印一个表格，对于每个N，给出 T 次实验中该数量的平均值。

要点分析

这题其实很简单，就是创建两个数组，然后利用二分查找数组a的每一个元素是否在数组b中就可以了。

参考答案

import java.util.Arrays;
import java.util.Random;

public class Thirty_nine {
    /**
     * @description: 二分查找（BinarySearch)方法，课本第5页
     * @param: a 要查找的数组
     * @param: key 要查找的元素
     * @return: 要查找的元素的索引
     */
    public static int rank(int[] a, int key) {
        int lo = 0;
        int hi = a.length - 1;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            if (key < a[mid]) {
                hi = mid - 1;
            } else if (key > a[mid]) {
                lo = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

    /**
     * @description: 建立大小为N的随机6位数整数数组
     * @param: N 要建立的数组大小
     * @return: 建立完成的数组
     */
    public static int[] build_array(int N) {
        int[] a = new int[N];
        Random ran = new Random();
        for (int i = 0; i < a.length; i++) {
            a[i] = ran.nextInt(1000000);
        }
        return a;
    }

    /**
     * @description: 打印一个表格，对于每个N，给出T次时间中的概述了的平均值
     * @param:  sum 存储表格信息的数组
     * @return:  Nothing
     */
    public static void print(int[] sum,int N) {
        double sums = 0;
        for (int i = 0; i < sum.length; i++) {
            sums += sum[i];
        }
        sums /= sum.length;
        System.out.println("当N = " + N + "时，平均值为： " + sums);
    }

    /**
     * @description: 计算同时存在于两个数组中的整数的数量
     * @param: N 要加你的数组大小
     * @param: T 将实验运行T遍
     * @return: T次实验后，每次实验所保存的同时存在于两个数组中的整数的数量
     */
    public static int[] count(int N, int T) {
        int[] sum = new int[T];
        for (int i = 0; i < T; i++) {
            int[] a = build_array(N);
            int[] b = build_array(N);
            Arrays.sort(b);
            for (int j = 0; j < N; j++) {
                if (rank(b,a[j]) != -1) { //如果a[j]也存在于数组b中，则sum[i]++
                    sum[i]++;

                }
            }
        }
        return sum;
    }

    public static void main(String[] args) {
        int T = Integer.parseInt(args[0]); //命令行传入T = 50
        int N = (int)Math.pow(10,3);
        int N2 = (int)Math.pow(10,4);
        int N3 = (int)Math.pow(10,5);
        int N4 = (int)Math.pow(10,6);
        print(count(N,T),N);
        print(count(N2,T),N2);
        print(count(N3,T),N3);
        print(count(N4,T),N4);
    }

}

输出：
当N = 1000时，平均值为： 0.94
当N = 10000时，平均值为： 96.3
当N = 100000时，平均值为： 9485.72
当N = 1000000时，平均值为： 632139.46