前言

符号表是一种存储键值对的数据结构，可以支持高效地插入、查找等操作。这里使用一个有序符号表的接口来表示这些操作，有序符号表保持键的有序性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class ST<Key extends Comparable<Key>, Value> {
    void put(Key key, Value value);
    
    Value get(Key key);
    
    int size();
    
    boolean isEmpty();
    
    Key max();
    
    Key min();
    
    int rank(Key key);
    
    Key select(int k);
    
    List<Key> keys(Key start, Key end);
    
    ........
}

二分查找

二分查找先将要查找的键和数组的中间键比较，如果被查找的键小于中间键，我们就在左子数组中继续查找，如果大于我们就在右子数组中继续查找，否则中间键就是我们要找的键。如果表中存在该键，此方法将返回该键的位置，否则，将返回该键应该插入的位置。

1
2
3
4
5
6
7
8
9
10
11
public int binarySearch(int[] nums, int target) {
    int start = 0;
    int end = nums.length - 1;
    while (start <= end) {
        int mid = (start + end) / 2;
        if (nums[mid] < target) start = mid + 1;
        else if (nums[mid] > target) end = mid - 1;
        else return mid;
	}
	return start;
}

查找数字第一次出现的索引

当一个有序数组中有重复的数字时，查找一个数字在数组中第一次出现的位置。例如，对于数组[1, 2, 3, 3, 3, 3, 4]，要查找的数字 3 的下标应该为 2 而不是 3。我们仅仅需要对普通的二分查找算法做一个简单的修改就能完成此功能：

1
2
3
4
5
6
7
8
9
10
11
public int binarySearchFirst(int[] nums, int target) {
    int start = 0;
    int end = nums.length - 1;
    
   	while (start <= end) {
        int mid = (start + end) / 2;
        if (nums[mid] < target) start = mid + 1;
        else if (nums[mid] >= target) end = mid - 1;    
    }
    return start;
}

查找数字最后一次出现的索引

同上

1
2
3
4
5
6
7
8
9
10
public int binarySearchLast(int[] nums, int target) {
    int start = 0;
    int end = nums.length - 1;
    
    while (start <= end) {
        int mid = (start + end) / 2;
        if (num[mid] <= target) start = mid + 1;
        else if(num[mid] > target) end = mid - 1;
    }
    return end;

二分查找实现有序符号表

使用一对平行的数组，一个存储 key，一个存储 value。

这份实现的核心是rank()方法，它返回了表中小于给定键的键的数量，等价于找到的键的位置或者键应该插入的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
public class BinarySearchST<Key extends Comparable<Key>, Value> {
    private Key[] keys;
    private Value[] values;
    private int N;

    public BinarySearchST(int capacity) {
        keys = (Key[]) new Comparable[capacity];
        values = (Value[]) new Comparable[capacity];
    }
    
    public int size() {
        return N;
    }
    
    public boolean isEmpty() {
        return N == 0;
    }
    
    public boolean contains(Key key) {
        return get(key) != null;
    }

    public Value get(Key key) 

    public void put(Key key, Value value) 

    public int rank(Key key) 

    public void delete(Key key) 
    
    public Key min() {
    	return keys[0];
	}

	public Key max() {
    	return keys[N - 1];
	}
    
    private void resize(int max) {
        Key[] keys = (Key[]) new Object[max];
        Value[] values = (Value[]) new Object[max];
        for (int j = 0; j < N; j++) {
            keys[j] = this.keys[j];
            values[j] = this.values[j];
        }
        this.keys = keys;
        this.values = values;
    }
}

排名

rank()是有序符号表的核心，它几乎和上面的二分查找相同，并且含有递归和迭代两种写法。

rank()包含以下性质：

  • 如果表中存在该键，返回键的位置，同时也是表中小于该键的键的数量；
  • 如果表中不存在该键，返回表中小于该键的数量；
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    // 递归的实现
    public int rank(Key key, int start, int end) {
        if (end < start) return;
        int mid = (start + end) / 2;
        int cmp = key.compareTo(keys[mid]);
        if (cmp < 0) 		// key < keys[mid]
            return rank(key, start, mid - 1);
        else if (cmp > 0) 	// key > keys[mid]
            return rank(key, mid + 1, end);
        else return mid;
    }

    // 迭代的实现
    public int rank(Key key) {
        int start = 0, end = N - 1;
        while (end <= start) {
            int mid = (start + end) / 2;
            int cmp = key.compareTo(keys[mid])
            if (cmp < 0) 				// key < keys[mid]
                end = mid - 1;		
            else if (key > keys[mid]) 	// key > keys[mid]
                start = mid + 1;
            else return mid;
        }
        return start;
    }

查找

get()方法根据rank()方法的返回值获得键相对应的值，如果键不存在则返回null

1
2
3
4
5
6
public Value get(Key key) {
    if (isEmpty()) return null;
    int i = rank(key);
    if (i < N && key.compareTo(keys[i]) == 0) return values[i];
    else return null;
}

插入

对于put()方法，如果键存在于表中，就更新键的值；否则将键存储到表中合适的位置，并将所有更大的键向后移动一格。这里实现键向后移动一格的是倒序的，从 N 逐渐向前循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 查找键，找到则更新值，否则创建新的元素
public void put(Key key, Value value) {
    if (N == keys.length) resize(2 * keys.length);
    
    int i = rank(key);
    if (i < N && key.compareTo(keys[i]) == 0) {
        values[i] = value;
        return;
    }
    for (int j = N; j > i; j--) {
        keys[j] = keys[j - 1];
        values[j] = values[j - 1];
    }
    keys[i] = key;
    values[i] = value;
    N++;
}

删除

删除的实现和插入大致相同。但是这里所有大的键需要向前移动一个，这里实现是正序的，从 i+1 逐渐向后循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void delete(Key key) {
    if (key == null) return;

    int i = rank(key);
    if (i >= N || key.compareTo(keys[i]) != 0) return;
    for (int j = i + 1; j < N; j++) {
        keys[j - 1] = keys[j];
        values[j - 1] = values[j];
    }
    N--;
    keys[N] = null;
    values[N] = null;

    if (N > 0 && N == keys.length / 4) resize(keys.length / 2);
}

向下取整和向上取整

1
2
3
4
5
6
7
8
9
10
public Key flooring(Key key) {
    int i = rank(key);
    if (key.compareTo(keys[i]) == 0) return keys[i];
    return --i < 0 ? null : keys[i - 1];
}

public Key celling(Key key) {
    int i = rank(key);
    return keys[i];
}

复杂度分析

二分查找的时间复杂度是对数级别的，最多为 logN+1，所以使用二分查找实现的有序符号表的查找操作的时间复杂度也是对数级别的。但是在插入时，因为需要移动数组元素，所以是线性级别的时间复杂度。

改进的小 tips

因为默认contains()的实现中调用了get()，所以当经常经常查找同一个键时，效率会很低。我们可以使用缓存的方式，将访问最频繁的键的位置保存在一个变量中，这样子不用每次都去调用rank()中的二分查找。