弱渣的google电面

pengzewen37 发表于 2015-10-7 06:37
从另一个帖子link到LZ这个帖子的，看到上面有人分析说1 -> 2 -> 3 -> 4 -> 2 -> 3 -> 4这样不对是因为没有 ...

因为题设中有p[]中存了0~n-1这n个数，如果有这样的cycle，则p[1]=p[4]=2，就不满足题设了

uuuouou 发表于 2015-10-6 20:55
因为题设中有p[]中存了0~n-1这n个数，如果有这样的cycle，则p[1]=p[4]=2，就不满足题设了

thx, 那题目就变简单了，任何一个index都是某一个cycle，那么遍历一遍直到下一个出现，找到这个周期的size就差不多解出来了

我把循环节存了一下，对a中有重复的无影响，p中有重复的表示会有影响，p中有重复的话，不能构成环了啊。。

我的C++代码，复杂度是O（N），假设p中无重复

1. vector<int> findKthVector(vector<int> &p, vector<int> &a, int k) {
   
2.     int n = p.size();
   
3.     unordered_map<int, pair<int, int> > cid;
   
4.     vector<vector<int> > cycle;
   
5.     vector<bool> visit(n, false);
   
6.     for (int i = 0; i < n; i++) {
   
7.         if (!visit[i]) {
   
8.             vector<int> c;
   
9.             c.resize(0);
   
10.             int pre = i;
    
11.             int t = i;
    
12.             do {
    
13.                 visit[t] = true;
    
14.                 cid[t] = make_pair(cycle.size(), c.size());
    
15.                 c.push_back(t);
    
16.                 t = p[t];
    
17.             } while (t != i);
    
18.             cycle.push_back(c);
    
19.         }
    
20.     }
    
21.     vector<int> ans;
    
22.     for (int i = 0; i < n; i++) {
    
23.         int t = a[i];
    
24.         int ci = cid[t].first;
    
25.         int pi = cid[t].second;
    
26.         int c_len = cycle[ci].size();
    
27.         int idx = (pi + c_len + k) % c_len;
    
28.         ans.push_back(cycle[ci][idx]);
    
29.     }
    
30.     for (auto e : ans)
    
31.         cout << e <<' ';
    
32.     return ans;
    
33. }

复制代码

第二题是个洗牌方法，p[] 是洗牌数组,作用是把第i个点map到第j个位置上去；那个反例要求p[2]=4 and p[2]=1, 这显然不可能；