A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© lovecx24 中级黑马   /  2013-12-5 21:05  /  1802 人查看  /  0 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

两道编程题
题目一:  编用lgn的时间复杂度找出有序数组A B(A B长度均为n个)的中位数
题目要求用lgn的复杂度,这就限制了我们归并后二分查找的思路。
现在只能是在数组AB之上进行直接进行二分查找。
思路如下:  a1 a2 a3 a4 a5 a6……an b1 b2 b3 b4 b5 b6……bn
1. 对AB首先进行一次二分查找,假设定位在了ai bi两个数上  
2. 比较ai bi的大小   
3. 如果ai>bi,那么数组A取ai左部的进行二分递归,B取bi右部进行二分递归
4. 重复步骤3,直至区间只剩下一个元素   
5. 这时可以进行判断数组A以这剩余元素的左右两侧的长度
6. 同时判断B中最后一个元素将B分割的效果  
7. 进行判断AB中的最后一个元素谁将是中位数  
8. 这就是这题的思路   
9. 程序完毕~这道题出的相当的巧妙, 这是一个的思路,不知道还有没其他思路?
题目二:  找出一段字符串中的最长重复字符串,比如:ababababcdsabab 那么在这个字符串中多次重复最长的字符串是ab 而且最长的应该是abababab 所以答案应该是abababab。

0 个回复

您需要登录后才可以回帖 登录 | 加入黑马