• 中文
    • English
  • 注册
  • 查看作者
  • 《算法第四版》课后练习题1.2.9答案

    习题1.2.9

    修改 BinarySearch(请见 1.1.10.1 节中的二分查找代码),使用 Counter 统计在有查找中被检查的键的总数并在查找全部结束后打印该值。提示:在 main() 中创建一个 Counter 对象并将它作为参数传递给 rank()。

    要点分析

    1.  BinarySearch

    1.1.10.1 节中的二分查找代码在课本第28页,代码如下:

    import edu.princeton.cs.algs4.In;
    import edu.princeton.cs.algs4.StdIn;
    import edu.princeton.cs.algs4.StdOut;
    
    import java.util.Arrays;
    
    
    public class BinarySearch {
        public static int rank(int key, int[] a) {
            int lo = 0;
            int hi = a.length - 1;
            while (lo <= hi) {
                int mid = lo + (hi - lo) / 2;
                if (key < a[mid]) hi = mid - 1;
                else if (key > a[mid]) lo = mid + 1;
                else return mid;
            }
            return -1;
        }
    
        public static void main(String[] args) {
            int[] whitelist = In.readInts(args[0]);
            Arrays.sort(whitelist);
            while (!StdIn.isEmpty()) {
                int key = StdIn.readInt();
                if (rank(key, whitelist) < 0) {
                    StdOut.println(key);
                }
            }
        }
    }

    2.  Counter

    关于Counter类的具体介绍可以查看课本第39页,这里给出该类的API

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

    3.  解题思路

    根据该题的提示,我们可以需要修改rank()方法的参数,将一个Counter对象传给rank,然后用increment()方法进行统计次数就可以了。

    值得注意的是,在main方法中,Counter要在while循环里生成对象,否则计数器会随着每次查找值而累加。

    参考答案

    import edu.princeton.cs.algs4.Counter;
    import edu.princeton.cs.algs4.In;
    import edu.princeton.cs.algs4.StdIn;
    import edu.princeton.cs.algs4.StdOut;
    
    
    public class BinarySearch {
        public static int rank(int key, int[] a, Counter c) {
            int lo = 0;
            int hi = a.length - 1;
            while (lo <= hi) {
                int mid = lo + (hi - lo) / 2;
                c.increment();
                if (key < a[mid]) hi = mid - 1;
                else if (key > a[mid]) lo = mid + 1;
                else return mid;
            }
    
            return -1;
        }
    
        public static void main(String[] args) {
            int[] whitelist = In.readInts(args[0]);
    
    //        Counter c = new Counter("Test");  //不可以放在这里,因为每次查找Counter计数器值没有被清零会累加
            System.out.println("请输入要查找的值:");
            while (!StdIn.isEmpty()) {
                int key = StdIn.readInt();
                Counter c = new Counter("Test");
                int r = rank(key, whitelist, c);
                if (r < 0) {
                    StdOut.println("没找到");
                } else {
                    System.out.println("被检查的键的总数为:" + c.tally()+ ", 下标为 " + r);
                }
                System.out.println("请输入要查找的值:");
            }
        }
    }
    
    
    args[0]传入一个文本文档地址,比如E:\Test\Test.txt
    Text.txt中的内容为1 3 2 4 6 5 7 9 8
    则输出:
    请输入要查找的值:
    9
    被检查的键的总数为:3, 下标为 7
    请输入要查找的值:
    6
    被检查的键的总数为:1, 下标为 4
    请输入要查找的值:
    0
    没找到

  • 0
  • 1
  • 0
  • 3.9k
  • 请登录之后再进行评论

    登录
  • 0
    [s-1]
  • 单栏布局 侧栏位置: