数据挖掘算法面试题
昨天去某厂面试数据挖掘，遇到了这么一道题
一个二维矩阵，右边的数值比左边的大，下边的数值比上边的大，设计一种算法，快速查找某个指定数字的位置
如下表所示的数据：
| 查找值： | 117 | |||||||||
| ——>右边的比左边的大 | ||||||||||
| 下边的比上边大 | 0 | 8 | 15 | 19 | 24 | 29 | 36 | 43 | 47 | 50 |
| 18 | 22 | 27 | 32 | 41 | 47 | 51 | 54 | 64 | 71 | |
| 35 | 39 | 49 | 59 | 66 | 75 | 80 | 82 | 86 | 93 | |
| 48 | 56 | 66 | 70 | 79 | 83 | 95 | 101 | 106 | 113 | |
| 73 | 83 | 88 | 94 | 100 | 106 | 115 | 123 | 130 | 136 | |
| 84 | 91 | 99 | 109 | 117 | 127 | 130 | 134 | 143 | 146 | |
| 105 | 111 | 114 | 120 | 128 | 134 | 143 | 152 | 155 | 158 | |
| 125 | 129 | 136 | 139 | 147 | 152 | 160 | 168 | 171 | 178 | |
| 139 | 148 | 154 | 160 | 168 | 175 | 182 | 187 | 197 | 202 | |
| 154 | 163 | 171 | 181 | 184 | 194 | 203 | 210 | 218 | 223 | |
在现场比较紧张，而且也不够时间，没有想出好的解决方法，今天上班时间折磨了一会，发现了这么一个好方法
时间复杂度估计就O(max(n,m))这样子吧，没有具体证明
基本的原理就是二分查找+对角限制
假设矩阵是n*m的
首先用二分查找找到最右列上比待查找值大的最小值，在上表中的话就是136
然后在最左列查找比待查找值小的最大值，在上表中的话就是105
这样就把待查找范围限制在下表范围内
| 73 | 83 | 88 | 94 | 100 | 106 | 115 | 123 | 130 | 136 |
| 84 | 91 | 99 | 109 | 117 | 127 | 130 | 134 | 143 | 146 |
| 105 | 111 | 114 | 120 | 128 | 134 | 143 | 152 | 155 | 158 |
接下来翻转比较，用二分查找找到最下面一行中比待查找值大的最小值，即120
然后在最上面一行查找比117小的最大值，即115
这样就把待查找范围限制在下表范围内
| 94 | 100 | 106 | 115 |
| 109 | 117 | 127 | 130 |
| 120 | 128 | 134 | 143 |
接下来继续翻转比较，找到左右俩边满足条件的最大值与最小值，即109和130
这样就把待查找范围限制在下表范围内
| 109 | 117 | 127 | 130 |
接下来一步二分查找即可匹配到117了，至此查找完毕......
某厂的面试官，给点机会吧亲。。。
【BootStrap】富编辑器，基于wysihtml5
在我的周围，已经有很多人在使用BootStrap，但对于任何一个带留言、评论、提问、文章编辑功的网站，编辑器永远是重中之重，显然，早期的编辑器完全没考虑过BootStrap的出现，或皮肤跟网站不匹配，或不支持BootStrap样式。
如果你了解BootStrap，肯定听说过bootstrap-wysihtml5（因为也没有其它的更多选择），但如果你稍稍使用一下，你便会发现，它不支持IE8 ！而BootStrap的最底支持就是IE8，为了一款编辑器，又大大限制了使用人群，即使在IE9下，也是稍有问题，严重依赖于编译器特性。
这里推荐一款跟BootStrap完美兼容的编辑器，wysihtml5。
事实上，bootstrap-wysihtml5的作者也提到他的这款编辑器的最初灵感就是来的自于wysihtml5。
Bootstrap-wysihtml5 is a javascript plugin that makes it easy to create simple, beautiful wysiwyg editors with the help of wysihtml5 and Twitter Bootstrap.
不过wysihtml5也有缺点：原作者快一年没更新了，作遗留了部份 Bug 未解决。
在我将其与BootStrap结合的过程中，顺手解决了能测试到的所有Bug，最于有了如下效果：
如果你想测试这款编辑器，可以在 这里 点击匿名提问或任何其它可以输入编辑的地方。
欢迎右键扒取。
编辑效果图一样：
