#面試編程題#一 個不能少：有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