• 中文
    • 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.7k
    • 请登录之后再进行评论

      登录
    • 0
      [s-1]
    • 赞助本站

      • 支付宝
      • 微信
      • QQ

      感谢一直支持本站的所有人!

      单栏布局 侧栏位置: