首页 > 代码库 > 剑指offer?
剑指offer?
1. 在一个m*n二维数组中,每一行都按照从左到右的递增顺排序,每一列都按照从上到下的顺序排序,请完成一个函数,输入这样一个二维数组和一个整数,判断数组中是否含有该整数。
1 2 8 9
2 4 9 12
4 7 9 12
6 8 11 15
这题有更好的做法吗?O(m+n)是最好的吗?网上说的分治法只对m=n的情况吧。
1 bool find(int** arr, int m, int n, int t) {2 int x = 0, y = n - 1;3 while (x < m && y >= 0) {4 if (t == arr[x][y]) return true;5 else (t > arr[x][y]) x++;6 else y--;7 } 8 return true;9 }
求第k个数,我觉得能想出来用堆就不错了。O(klgk),就是维护一个堆。
http://www.quora.com/How-can-you-efficiently-determine-the-k-th-maximum-element-in-a-MxN-sorted-matrix
2 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并输出它的后序遍历序列。 (本题可以直接输出来,不用先还原出二叉树)
剑指offer?
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。