2018年4月2日

【算法】1.1. 基础编程模型

正文

二分查找与白名单过滤

想象一家信用卡公司,它需要检查客户的交易账号是否有效。为此,它需要:

  • 将客户的账号保存在一个文件中,我们称它为“白名单”;
  • 从标准输入中得到每笔交易的账号;
  • 在标准输出中打印所有与任何客户无关的账号,公司很可能拒绝此类交易。

在一家有上百万客户的大公司中,需要处理数百万甚至更多的交易都是很正常的。暴力实现处理大量输入(比如含有 100 万个条目的白名单和 1000 万条交易)非常慢。没有如二分查找或者归并排序这样的高效算法,解决大规模的白名单问题是不可能的。

以下是示例程序:

package ch1;

import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

import java.util.Arrays;

/**
 * Created by plough on 2018/4/1.
 */
public class BinarySearch {
    public static int rand(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 (rand(key, whitelist) < 0) {
                StdOut.println(key);
            }
        }
    }
}

 

答疑

  • Java字节码是程序的一种低级表示,可以运行于Java的虚拟机。将程序抽象为字节码可以保证Java程序员的代码能够运行在各种设备之上。
  • 我们会使用int类型表示较小的数(小于10个十进制位)而使用long表示10亿以上的数。
  • Math.abs(-2145483648) 的返回值还是 -2145483648。这个奇怪的结果(但的确是真的)就是整数溢出的典型例子。
  • 如何才能将一个double变量初始化为无穷大?使用Java内置常数:Double.POSITIVE_INFINITY 和 Double.NEGATIVE_INFINITY。
  • Java表达式1/0和1.0/0.0的值是什么?第一个表达式会产生一个运行时除以零异常(它会终止程序);第二个表达式的值是Infinity(无穷大)。
  • 负数的除法和余数的结果是什么?表达式a/b的商会向0取整;a%b的余数的定义是(a/b)*b + a%b恒等于a。例如-14/3和14/-3的商都是-4,但-14%3是-2,而14%-3是2。
  • 一个 for 循环和它的 while 形式有什么区别?for 循环头部的代码和 for 循环的主题代码在同一个代码段之中。在一个典型的 for 循环中,递增变量一般在循环结束之后都是不可用的;但在和它等价的 while 循环中,递增变量在循环结束之后仍然是可用的。这个区别常常是使用 while 而非 for 循环的主要原因。

You may also like...

发表评论

电子邮件地址不会被公开。 必填项已用*标注


*