我有一个编写一个算法(不是任何特定的语言,只是伪代码)的任务,它接收一个矩阵[size:M x N],该矩阵的排序方式是所有行都被排序,所有的列都是单独排序,并在此矩阵中查找特定值.我需要编写我能想到的最节省时间的算法.
矩阵看起来像:
1 3 5
4 6 8
7 9 10
我的想法是从第一行和最后一列开始,只需检查值,如果它更大,那么它是否小于左边并继续这样做,直到找到该值或直到索引超出界限(以防万一)该值不存在).该算法在线性复杂度O(m + n)下工作.我被告知有可能以对数复杂度这样做.可能吗？如果是的话,怎么样？
不久前,我们得到了一个编写ac程序的赋值,该程序使用d-ary max-heap(每个节点最多有d个子节点的堆)对n个数字的数组进行排序.程序需要让用户输入d的值,一个介于2和数组大小之间的值.当我检查我的程序时,我偶然输入1作为d的值,并且不知何故算法成功地使用1-ary堆正确地对数组进行排序,尽管它比d的正常值花费了更多的时间.
怎么可能？1-ary堆甚至不是堆,它就像列表一样,每个节点只有一个子节点.任何人都可以解释这种排序是如何发生的
我目前正在攻读算法入门考试,我遇到了一个我无法解决的问题,问题是:你有一个n个整数的数组,前m个元素是偶数,剩下的元素很奇怪.您需要编写一个算法来查找m的值(找到最后一个偶数的索引),并且时间复杂度为O(log m).
我想做类似于二分搜索的事情,如果奇数就向左移动,如果直到我发现索引是偶数并且他的下一个是奇数,则向右移动但是这个东西在O(log n)而不是O(记录m).