coding everyday

编程面试题 https://interview.codeplex.com

C++博客 首页 新随笔 联系 聚合 管理
  12 Posts :: 2 Stories :: 7 Comments :: 0 Trackbacks

#面试编程题# 个不能少:有k个有序的数组,请找到一个最小的数字范围。使得这k个有序数组中,每个数组都至少有一个数字在该范围中。例如:1:{ 4, 10, 15, 24, 26 }2: { 0, 9, 12, 20 }3: { 5, 18, 22, 30 }。所得最小范围为[20,24],其中,202中,223中,241中。

 

刚看到这个问题的时候,感觉好难啊,这怎么才能找出来呢?有时候我觉得多看几遍题目还是有好处的,读书百遍其义自见啊。这个题目有几个关键点:所有的数组是有序的、每个数组至少有一个数字出现在那个范围里。

 

围绕着后面一点,我想,我们至少得维护一个kitem东西,然后每次从这个东西里面移掉一个放进去一个,尼玛,这怎么感觉像是个队列嘛。队列?把最小的移掉,放进去它所在数组的后一个。咦,东西(队列)里面是不是还是k个元素,并且来自k个数组?

 

看上去可行,组织下思路。

 

如果我们这里的数据结构用队列显然是不能满足要求的,因为我们不能很快得出队列中最小和最大的值,也就得不到范围,那么如果队列是有序的,是不是可以解决这个问题呢?简单的推敲下,答案是肯定的。我们用priority_queue应该是可以解决这个问题的。

 

  1. 首先,我们把k个数组中的第一个元素都压到p_q里面去,记下来最大的那个,因为最小的那个可以通过top()得到。只需要最大的那个就能得到range,对吧。如例中的:p_q: { 0, 4, 5 }, max_data: 5

 

  1. 然后,把第一个(最小的)弹出来,这个时候得到一个range,如果这个range比之前的小,用这个range。把弹出来的那个元素所在的数组的后一个压进去,如果这个值比最大的那个大,把它标成最大的。如例中:0出来,9进去,p_q: { 4, 5, 9 } max_data: 9, range {0, 5}

 

  1. 重复步骤2,直到某一个数组遍历完毕即可。为什么?显而易见嘛,没东西压了啊。:D

 

为了能比较好的处理,定义了一些辅助的数据结构:data就是被压的那个东西,用来定义某个数组的某个元素,方便找它对应的下一个元素;range就是我们最终要求的范围。

 

有人会说,面试算法题,用库里的数据结构不太好吧。这个我同意,有些算法题确实用库里的东西,直接就秒了。如果在面试过程中,面试官也提出类似的质疑,那么我们自己实现个类似的数据结构总OK吧?这里我们也可以很轻松的实现一个满足要求的数据结构啊。姑且称之为,sorted_list


 1 template<typename T>
 2 struct node{
 3     T data;
 4     node *next;
 5 };
 6 
 7 template<typename T>
 8 class sorted_list {
 9 public:
10     void push(const T& t);
11     void pop();
12     T top();
13     // even we can provide both smallest & biggest value, by that way, we don't need to have max_data
14     T bottom();
15 private:
16     node<T> head;
17     node<T> tail;
18 };

部分代码:
get_shortest_range

数据结构:
data structures

完整代码

附:出题人的分析。
http://mp.weixin.qq.com/mp/appmsg/show?__biz=MjM5ODIzNDQ3Mw==&appmsgid=10000075&itemidx=1&sign=46da65072c3062638e80f16599498508
我觉得本质应该跟我的算法是一样的吧。:D, :P
posted on 2013-07-18 10:14 everyday 阅读(284) 评论(0)  编辑 收藏 引用 所属分类: Algorithm

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理