xiaoyuzdy / algorithms Goto Github PK

计算最远的一对，distant方法应该是不对的。因为排序的时间复杂度是O(nlog(n))，所以先排序，不管怎么样都不可能在线性复杂度内完成。
正确的做法应该是不排序，直接扫描两边，第一遍找出最大值，第二遍找出最小值，这两个值就是最远的一对。

您好！这里书中的代码，我感觉root.color = RED;那两句其实没有真正用处，即使去掉也不会影响，不知道对不对。（我用"SEARCHEXAMPLE"试过没有什么区别）
还有，就是moveRedLeft函数中右旋左旋那里，是不是在if语句中旋转完后再加个flipColors(h);才和树中正文部分情况一致，虽然即使不加也不会影响最后结果，因为有回溯修正。但感觉代码是正文讲的优化过的，感觉贴一个按照正文所讲步骤写的代码，然后再贴优化过的代码更好理解一点。
希望您有空能帮忙看下，谢谢！
还有，moveRedLeft里好像也可以像deleteMax一样直接h = rotateLeft(h)就行了，这样回溯的时候可能要多执行一些操作，但效果一样的。

可以用lg(n)方法解決，你好好想想，結合數學圖像，某個點如果不是local minimum，那麼這點的圖像要麼是上升坡，要麼是下降坡，上身坡說明，local min在左邊，下降坡度，說明有local min在右邊. 不過題目有問題的地方是。local min不是a[i-1]<a[i]<a[i+1],根據數學應該是a[i]<[a-1] && a[i]<a[i+1].

您好，我最近在看《算法》，里面的索引优先队列有地方理解不了，insert方法里，直接令qp[k] = N，但是后面不是swim(N)了吗？这样索引k的位置应该不是N了吧，我自己在网上查了很多，但都是这样的，我感觉理解不了，希望您能给我讲解一下，谢谢。另外，星星已给。

您用的方法是先找出最小下标，然后再递增下标直到数组值不再等于key，但是极端情况下，比如整个数组都是同一个数，那这样的方法的时间复杂度就是N了吧（题目要求的是logN）

我想是不是可以利用您在上一题中使用的找最小下标的方法，稍微改一下符号，再写一个找最大下标的方法，这样配合的话极端情况下时间复杂度就可以与logN成正比了

（我是初学者，如果说的不对请见谅）

howMany()方法，在最坏情况下，复杂度为O(n)，如果一个数组的所有元素都是指定的可以，那循环就会执行n次。
我觉得正确的做法应该是，参考前一题，先找出最小索引，再找出最大索引，这两个操作都是对数级的复杂度，然后直接就能求出结果。