#面试编程题#一 个不能少：有k个有序的数组，请找到一个最小的数字范围。使得这k个有序数组中，每个数组都至少有一个数字在该范围中。例如：1:{ 4, 10, 15, 24, 26 }；2: { 0, 9, 12, 20 }；3: { 5, 18, 22, 30 }。所得最小范围为[20,24]，其中，20在2中，22在3中，24在1中。
刚看到这个问题的时候，感觉好难啊，这怎么才能找出来呢？有时候我觉得多看几遍题目还是有好处的，读书百遍其义自见啊。这个题目有几个关键点：所有的数组是有序的、每个数组至少有一个数字出现在那个范围里。
围绕着后面一点，我想，我们至少得维护一个k个item的东西，然后每次从这个东西里面移掉一个放进去一个，尼玛，这怎么感觉像是个队列嘛。队列？把最小的移掉，放进去它所在数组的后一个。咦，东西（队列）里面是不是还是k个元素，并且来自k个数组？
看上去可行，组织下思路。
如果我们这里的数据结构用队列显然是不能满足要求的，因为我们不能很快得出队列中最小和最大的值，也就得不到范围，那么如果队列是有序的，是不是可以解决这个问题呢？简单的推敲下，答案是肯定的。我们用priority_queue应该是可以解决这个问题的。
- 首先，我们把k个数组中的第一个元素都压到p_q里面去，记下来最大的那个，因为最小的那个可以通过top()得到。只需要最大的那个就能得到range，对吧。如例中的：p_q: { 0, 4, 5 }, max_data: 5
- 然后，把第一个（最小的）弹出来，这个时候得到一个range，如果这个range比之前的小，用这个range。把弹出来的那个元素所在的数组的后一个压进去，如果这个值比最大的那个大，把它标成最大的。如例中：0出来，9进去，p_q: { 4, 5, 9 } max_data: 9, range {0, 5}
- 重复步骤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
1 range get_shortest_range(int **p, int *array_size, int k) {
2 // The pq keeps k item in the queue, it makes sure there is one item from every array
3 priority_queue<data> pq;
4 data max_data;
5 range result;
6
7 // Push all first items of arrays into priority queue;
8 for (int i=0; i<k; i++) {
9 data dd(p, i, 0);
10 pq.push(dd);
11
12 if (dd.value() > max_data.value()) {
13 max_data = dd;
14 }
15 }
16
17 while (true) {
18 data current = pq.top();
19 if (max_data.value() - current.value() < result.value()) {
20 result.start = current.value();
21 result.end = max_data.value();
22 }
23 pq.pop();
24 // If one of arrays is running out, it's time to say goodbye.
25 if (current.data_index >= array_size[current.array_index] - 1)
26 break;
27
28 // Push next item for 'current' in its array
29 data next(current.arrays, current.array_index, current.data_index + 1);
30 pq.push(next);
31 if (next.value() > max_data.value())
32 max_data = next;
33 }
34
35 return result;
36 }数据结构：
data structures
1 // Represent an item within one array
2 struct data {
3 int **arrays;
4 int array_index;
5 int data_index;
6
7 data() : arrays(nullptr) {
8 }
9
10 data(int **pp, int ai, int di) {
11 this->arrays = pp;
12 this->array_index = ai;
13 this->data_index = di;
14 }
15
16 data(const data& d) {
17 this->arrays = d.arrays;
18 this->array_index = d.array_index;
19 this->data_index = d.data_index;
20 }
21
22 data& operator=(const data& d) {
23 if (&d != this) {
24 this->arrays = d.arrays;
25 this->array_index = d.array_index;
26 this->data_index = d.data_index;
27 }
28
29 return *this;
30 }
31
32 int value() const {
33 if (arrays == nullptr)
34 return 0;
35
36 return arrays[array_index][data_index];
37 }
38
39 bool operator<(const data &d1) const {
40 return this->value() > d1.value();
41 }
42 };
43
44 struct range {
45 int start;
46 int end;
47
48 range() :
49 start(numeric_limits<int>::min()), end(numeric_limits<int>::max()) {
50 }
51
52 int value() {
53 if (end - start < 0)
54 return numeric_limits<int>::max();
55
56 return end - start;
57 }
58 }; 完整代码附：出题人的分析。
http://mp.weixin.qq.com/mp/appmsg/show?__biz=MjM5ODIzNDQ3Mw==&appmsgid=10000075&itemidx=1&sign=46da65072c3062638e80f16599498508
我觉得本质应该跟我的算法是一样的吧。:D, :P