Algorithms
Algorithms copied to clipboard
AlgorithmsTest is Code from the book "Algorithms" (4th ed.) by Robert Sedgewick and Kevin Wayne,算法第四版书中代码以及后面的习题,AlgorithmsExercise是一些牛客网上的题目,AlgorithmsReplenish是一些算法的...
计算最远的一对,distant方法应该是不对的。因为排序的时间复杂度是O(nlog(n)),所以先排序,不管怎么样都不可能在线性复杂度内完成。 正确的做法应该是不排序,直接扫描两边,第一遍找出最大值,第二遍找出最小值,这两个值就是最远的一对。
howMany()方法,在最坏情况下,复杂度为O(n),如果一个数组的所有元素都是指定的可以,那循环就会执行n次。 我觉得正确的做法应该是,参考前一题,先找出最小索引,再找出最大索引,这两个操作都是对数级的复杂度,然后直接就能求出结果。
练习1_4_11
您用的方法是先找出最小下标,然后再递增下标直到数组值不再等于key,但是极端情况下,比如整个数组都是同一个数,那这样的方法的时间复杂度就是N了吧(题目要求的是logN) 我想是不是可以利用您在上一题中使用的找最小下标的方法,稍微改一下符号,再写一个找最大下标的方法,这样配合的话极端情况下时间复杂度就可以与logN成正比了 (我是初学者,如果说的不对请见谅)
可以用lg(n)方法解決,你好好想想,結合數學圖像,某個點如果不是local minimum,那麼這點的圖像要麼是上升坡,要麼是下降坡,上身坡說明,local min在左邊,下降坡度,說明有local min在右邊. 不過題目有問題的地方是。local min不是a[i-1]
您好!这里书中的代码,我感觉root.color = RED;那两句其实没有真正用处,即使去掉也不会影响,不知道对不对。(我用"SEARCHEXAMPLE"试过没有什么区别) 还有,就是moveRedLeft函数中右旋左旋那里,是不是在if语句中旋转完后再加个flipColors(h);才和树中正文部分情况一致,虽然即使不加也不会影响最后结果,因为有回溯修正。但感觉代码是正文讲的优化过的,感觉贴一个按照正文所讲步骤写的代码,然后再贴优化过的代码更好理解一点。 希望您有空能帮忙看下,谢谢! 还有,moveRedLeft里好像也可以像deleteMax一样直接h = rotateLeft(h)就行了,这样回溯的时候可能要多执行一些操作,但效果一样的。
有个问题想请教
您好,我最近在看《算法》,里面的索引优先队列有地方理解不了,insert方法里,直接令qp[k] = N,但是后面不是swim(N)了吗?这样索引k的位置应该不是N了吧,我自己在网上查了很多,但都是这样的,我感觉理解不了,希望您能给我讲解一下,谢谢。另外,星星已给。