又是描述较长的一个题。题目本身就是说给定一个数组A，如果两个数在A中相邻出现，就叫做这两个数在A中相邻相邻。数组Ｂ和数组A相邻，如果同时满足
（1） B[0] = A[0]
(2) B[M - 1] = A[N - 1] M, N分别是Ｂ和A的长度
（3） B中相邻的两个数在A中也相邻
求出一个和数组Ａ相邻的数组B最短的长度。
数据范围：
N 1..10^5
每个数的范围 整数[-2147483648..+2147483647]
要求复杂度：时间O(NlogN),空间O(N)
分析： 首先数组B肯定存在，因为可以让B=A。我们可以按照相邻关系建立一个无向图。如果两个数在A种相邻，则这两个数有条边。所以节点数是O(N)，变数是 O(2N) = O(N)。
然后B的长度其实就是从A[0]到A[N-1]最短路的长度，bfs就行。。。。logN的原因是我们要用map，因为数据范围不能直接放到下标里……还要注意B可以直有一个元素的。如果A[0] == A[N - 1]，那么取B[0] = A[0]，长度为1满足条件。
代码：
// you can also use includes, for example:
// #include <algorithm>
#include <set>
#include <map>
#include <queue>
int solution(const vector<int> &A) {
// write your code here...
int n = A.size(),i,x,y;
if (A[0] == A[n - 1]) {
return 1;
}
map<int, set<int> > e;
map<int,int> d;
for (i = 1; i < n; ++i) {
e[A[i]].insert(A[i - 1]);
e[A[i - 1]].insert(A[i]);
}
map<int,set<int> >::iterator t;
set<int>::iterator it;
map<int,int>::iterator tt;
queue<int> q;
d[A[0]] = 1;
for (q.push(A[0]);;q.pop()) {
x = q.front();
t = e.find(x);
if (t != e.end()) {
y = d[x] + 1;
for (it = t->second.begin(); it != t->second.end(); ++it) {
if (*it == A[n - 1]) {
return y;
}
tt = d.find(*it);
if (tt == d.end()) {
if (*it == A[n - 1]) {
return y;
}
d.insert(make_pair(*it, y));
q.push(*it);
}
}
}
}
return y;
}