AI and Big Data

Algorithm

查找两个排序数组的中位数

题目是:求两个排序数组的中位数。
设:两个排序的数组a[m], b[n],求a和b数组的中位数。
算法是:
mid_a是数组a的中位数index,同理mid_b是数组b的中位数索引
1. 如果a[mid_a] == b[mid_b] 中位数为a[mid_a]

2. 如果a[mid_a] < b[mid_b], 递归查找a(mid_a + 1, m - 1), b(0, mid_b),因为a[mid_a]比较小,不可能作为下一次查询的中位数

3. 如果a[mid_a] > b[mid_b], 递归查找a(0, mid_a), b(mid_b + 1, n - 1),因为b[mid_b]比较小,不可能作为下一次查询的中位数

4. 当只少于4个元素需要查找时递归停止,merge这少于4的元素,求出中位数。这里需要考虑奇偶数的情况,只剩下2个或3个元素,不如只考虑4个简单。

注意:这里求上中位数,当n为奇数时,中位数是唯一的,出现位置为n/2;当n为偶数时候,存在两个中位数,数组index从0开始,位置分别为n/2 - 1(上中位数)和n/2(下中位数)。

Continue reading

Algorithm

Dijkstra Algorithm

计算单源最短路径的算法有Bellman-Ford算法,主要是计算带负权有向图的单源最短路径。第二种算法:对于DAG图(Directed Acyclic Graph, 有向无环图)可以通过拓扑排序后再计算单源最短路径。第三,可以使用BFS(广度优先搜索)计算单源最短路径。第四,就是著名的Dijkstra算法,要求有向图的所有边的权值非负,当然图可以不是DAG图。

Continue reading