我大概想到一个启发式的方法，首先假设矩阵中的每个元素都不相同，遍历m*n个元素并按照升序排列，在排序的过程中要保留每个矩阵元素的行列索引，即排序后元素a[i,j]是i行j列的元素，排序后的元素放在数组S中。
    那么，整个矩阵中最小的元素肯定是鞍点。之后判断第二小的元素是否同S中比它小的的某一个元素同行或同列，如果否，则这个元素也是一个鞍点。以此类推。这样的鞍点至多有min(m,n)个，或者S中的元素都进行过筛选，则算法停止。
    如果考虑矩阵中的元素有可能相等，那么最坏情况下，鞍点不存在。

[quote] 那么，整个矩阵中最小的元素肯定是鞍点。[/quote]

为什么有这个结论？


LZ的算法是O(n*m)，已经很不错了；

可以把两个过程重叠起来：
找每一行的最小元素下标，找到后立即从最小元素下标所在列开始验证它是不是该列的最大元，如果是就是鞍点，如果找到一个元素比它大，就可以直接否定它，不再继续比较。

如果矩阵的数据结构组织得好，可能会有更好的效率，选最小元或最大元，如果在堆里面只有O(1)的时间，如果在内部再维护一个堆就会有更好的效果，像直接法里有列主元素消去法，动态地找最大元使用堆就会有更好的效果，换句话说，如果在一个动态的矩阵里寻找可变动的鞍点，就有提高性能的可能，如果矩阵是静态的，恐怕很难提高了。

比如你是在矩阵运算的过程中不断地找鞍点（为了计算的需要），就有可能提高。