搜索算法的应用

1. 寻找重复元素

在排序应用中也可以寻找重复元素,但是使用符号表则更为高效(特别是散列实现)。

将数组遍历一遍,随后查找表内是否存在这一元素,如果不存在则添加进表中,如果存在,则说明找到了重复元素

分析:遍历一遍数组所需要的时间是 O(N)O(N),由于散列表的查找和插入都是常数级别的,所以整体的复杂度是 O(N)O(N)

排序则需要 O(NlogN)O(NlogN) 的时间,在最坏情形下需要遍历一遍整个数组(O(N)O(N)),时间复杂度是 O(N+NlogN)O(N + NlogN) 比符号表稍大。

2. 字典实现

符号表的键值对特性最适合实现的就是一个字典类,其中包括电话黄页字典账户信息 等等

3. 过滤器

可以用符号表过滤重复元素,建立黑名单和白名单等。这主要是依赖于符号宝的高效的查找操作。

4. 反向索引

可以将键和值互换,建立反向索引,实现相互搜索。

5. 矩阵乘法

矩阵乘法中的 0 是无用的,所以我们可以通过构建一个 向量类 ,使用一个符号表, 键值为向量中不为零元素的数组索引和相应的值。

所以,我们就可以使用一个 向量数组 来代表矩阵;

通过向量点乘的结果,来得到新矩阵的某个元素的值。

进行点乘时,只需要查找出元素,再依照储存的索引找到相应的值相乘即可

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
public class SparseVector {
private HashST<Integer, Double> st;
public SparseVectro() {
st = new HashST<Integer, Double>();
}

public int size() {
return st.size();
}

public void put(int i, double x) {
st.put(i, x);
}

public double get(int i) {
if (!st.contains(i)) {
return 0.0;
}
else {
return st.get(i);
}
}

public double dot(double[] that) {
double sum = 0.0;
for (int i : st.keys()) {
sum += that[i] * this.get(i);
}
return sum;
}
}