问个G家面试题 - 未名空间MITBBS历史存档

P*d2016-08-16 07:08

1 楼

输入是一个字符串数组，一个int数组，输入的字符串数组是另外一个字符串数组通过
int数组变换得到的，int数组的值代表的是原来这位置上的字符串经过变换后的坐标，
然后输出是求变换之前的字符串数组，要求用线性时间，o(1)额外空间
打个比方，比如一个字符串数组是"cat", "rabbit","dog", "mouse"，int数组给的2,0
,3,1，意思是string数组第0个词是cat，它本来的位置是在哪呢，我们要看int数组，
int数组的0在index 1上，所以说cat之前应该是1号位的，同理rabbit在string数组的1
号位，而index数组3号位的值是1，说明rabbit这个词之前应该在3号位上的，依次类推
，所以变换前的字符串数组应该是 dog, cat, mouse, rabbit
再打个比方，如果输入是Cat mouse dog rabbit和2,0,1,3，输出也会是dog, cat,
mouse, rabbit
再打个比方，如果输入是Cat mouse dog rabbit, tiger, lion和2,0,1,3,5,4，输出会
是dog, cat ,moutse, rabbit, lion, tiger
这个题感觉从变换前的数组求变换后的数组很好做，假设string数组是S，int数组是A
，直接一位一位循环遍历，当A[i] != i 时候把A[i] 与 A[A[i]]以及S[i] 与S[A[i]]
一直调换就可以了
但这个题是要从变换后的数组求变换前的数组，做了半天也没做出个好的解法，估计跪
了

l*g2016-08-16 07:08

2 楼

楼主有点紧张了，我还是没理解题目的输入输出是什么

P*d2016-08-16 07:08

3 楼

是比较绕，这个是反向转换，如果是正向转换是这样
再打个比方，如果输入dog, cat ,moutse, rabbit, lion, tiger和2,0,1,3,5,4，然后
数字数组的index代表字符串数组对应的元素的实际位置，那么得到的是输出是 Cat
mouse dog rabbit, tiger, lion，因为cat在数组中index是1，对应的数字数组1号位
的值是0,代表cat实际应该在0号位，转换之后就是 Cat mouse dog rabbit, tiger,
lion
但这个题是反过来，给你的字符串数组输入是上面我举的例子的输出Cat mouse dog
rabbit, tiger, lion
，而数字数组还是和上面例子一样，是2,0,1,3,5,4，要你想办法得到上面例子的字符
串输入og, cat ,moutse, rabbit, lion, tiger

【在 l**g 的大作中提到】

: 楼主有点紧张了，我还是没理解题目的输入输出是什么

p*d2016-08-16 07:08

4 楼

lz举的例子，难道不是直接拿数字数组的书作为字符串数组的index，按顺序输入就好
了？

a*e2016-08-16 07:08

5 楼

so easy

,0
的1

【在 P****d 的大作中提到】

: 输入是一个字符串数组，一个int数组，输入的字符串数组是另外一个字符串数组通过
: int数组变换得到的，int数组的值代表的是原来这位置上的字符串经过变换后的坐标，
: 然后输出是求变换之前的字符串数组，要求用线性时间，o(1)额外空间
: 打个比方，比如一个字符串数组是"cat", "rabbit","dog", "mouse"，int数组给的2,0
: ,3,1，意思是string数组第0个词是cat，它本来的位置是在哪呢，我们要看int数组，
: int数组的0在index 1上，所以说cat之前应该是1号位的，同理rabbit在string数组的1
: 号位，而index数组3号位的值是1，说明rabbit这个词之前应该在3号位上的，依次类推
: ，所以变换前的字符串数组应该是 dog, cat, mouse, rabbit
: 再打个比方，如果输入是Cat mouse dog rabbit和2,0,1,3，输出也会是dog, cat,
: mouse, rabbit

P*d2016-08-16 07:08

6 楼

正向转换是你说的这样，比如
dog, cat ,moutse, rabbit, lion, tiger和2,0,1,3,5,4，用数字数组的输出会
是Cat mouse dog rabbit, tiger, lion，很直观的就是dog数字数组对应的是2，所以
dog放到2号位，cat数字数组对应的值是0，放到0号位
但现在题目的要求是给你的输入是Cat mouse dog rabbit, tiger, lion和2,0,1,3,5,4
，要你得到dog, cat ,moutse, rabbit, lion, tiger，也就是说一个字符串数组，按
你下面说的方法变成另外一个字符串数组之后，让你再想办法变回来

【在 p****d 的大作中提到】

: lz举的例子，难道不是直接拿数字数组的书作为字符串数组的index，按顺序输入就好
: 了？

P*d2016-08-16 07:08

7 楼

请赐教啊，我搞了好久没搞出来

【在 a****e 的大作中提到】

: so easy
:
: ,0
: 的1

g*g2016-08-16 07:08

8 楼

,4
例子不是很简单吗？
input_string="cat,mouse,..."
input_sequence="2,0,..."
不就是
output
=input_string[input_sequence]
=input_string[2,0,...]
="cat,mouse,..."[2,0,...]
="dog,cat,..."

【在 P****d 的大作中提到】

: 正向转换是你说的这样，比如
: dog, cat ,moutse, rabbit, lion, tiger和2,0,1,3,5,4，用数字数组的输出会
: 是Cat mouse dog rabbit, tiger, lion，很直观的就是dog数字数组对应的是2，所以
: dog放到2号位，cat数字数组对应的值是0，放到0号位
: 但现在题目的要求是给你的输入是Cat mouse dog rabbit, tiger, lion和2,0,1,3,5,4
: ，要你得到dog, cat ,moutse, rabbit, lion, tiger，也就是说一个字符串数组，按
: 你下面说的方法变成另外一个字符串数组之后，让你再想办法变回来

g*e2016-08-16 07:08

9 楼

没看懂，就这么简单？

P*d2016-08-16 07:08

10 楼

没太看懂你写的，但我如果对你的符号理解正确的话这题的关系应该是
output_string[inputSequence] = input_String，其实就是让你反向mapping回去
你给的是正向mapping关系

【在 g*******g 的大作中提到】

:
: ,4
: 例子不是很简单吗？
: input_string="cat,mouse,..."
: input_sequence="2,0,..."
: 不就是
: output
: =input_string[input_sequence]
: =input_string[2,0,...]
: ="cat,mouse,..."[2,0,...]

l*g2016-08-16 07:08

11 楼

可以直接给几个输入输出吗，我感觉智商有点不够用
输入1:
输出1:

P*d2016-08-16 07:08

12 楼

我原贴中有啊

【在 l**g 的大作中提到】

: 可以直接给几个输入输出吗，我感觉智商有点不够用
: 输入1:
: 输出1:

a*g2016-08-16 07:08

13 楼

我纠正一下：
lz举的例子，难道不是直接拿数字数组的数作为字符串数组的index，按顺序输出就好
了？

【在 p****d 的大作中提到】

: lz举的例子，难道不是直接拿数字数组的书作为字符串数组的index，按顺序输入就好
: 了？

n*n2016-08-16 07:08

14 楼

原题要求不能有额外空间，时间复杂度为O(1);
应该就是说只能对 input string 数组，根据input int数组在数组内操作；
Cat mouse dog rabbit
2 0 1 3
一个想法就是不停的swap, Cat对应2, Cat 跟 dog做swap, 变成
dog mouse cat rabbit
2 0 1 3
然后因为dog原来对应的是1, cat 在跟 mouse做swap,
dog cat mouse rabbit
2 0 1 3
mouse 原来对应的是0, cat本来就是0, 前面就ok了，不过后面怎么继续到rabbit?

n*n2016-08-16 07:08

15 楼

可以用一个int 记录当前排好序的数目，比如这题前三个是一个loop，前三个排序不需
要最后一个数，排好后int为三，就在从第四个开始？

【在 n*******n 的大作中提到】

: 原题要求不能有额外空间，时间复杂度为O(1);
: 应该就是说只能对 input string 数组，根据input int数组在数组内操作；
: Cat mouse dog rabbit
: 2 0 1 3
: 一个想法就是不停的swap, Cat对应2, Cat 跟 dog做swap, 变成
: dog mouse cat rabbit
: 2 0 1 3
: 然后因为dog原来对应的是1, cat 在跟 mouse做swap,
: dog cat mouse rabbit
: 2 0 1 3

c*o2016-08-16 07:08

16 楼

如果我没理解错的话，反着变也可以转化成正着变，但int数列要变一下：
比如int数列第i个位置上是a[i]，反着变的时候只需要换成a[a[i]]应该就可以了。

g*g2016-08-16 07:08

17 楼

没有说int数组不可以变吧？那就一直换，换到没办法换为止。
a b c d
2 0 3 1
c b a d
x 0 3 1
c b d a
x 0 x 1
c a d b
x 0 x x
c a d b
x x x x

G*n2016-08-16 07:08

18 楼

看不出有什么trick…一个一个swap

,0
的1

【在 P****d 的大作中提到】

: 输入是一个字符串数组，一个int数组，输入的字符串数组是另外一个字符串数组通过
: int数组变换得到的，int数组的值代表的是原来这位置上的字符串经过变换后的坐标，
: 然后输出是求变换之前的字符串数组，要求用线性时间，o(1)额外空间
: 打个比方，比如一个字符串数组是"cat", "rabbit","dog", "mouse"，int数组给的2,0
: ,3,1，意思是string数组第0个词是cat，它本来的位置是在哪呢，我们要看int数组，
: int数组的0在index 1上，所以说cat之前应该是1号位的，同理rabbit在string数组的1
: 号位，而index数组3号位的值是1，说明rabbit这个词之前应该在3号位上的，依次类推
: ，所以变换前的字符串数组应该是 dog, cat, mouse, rabbit
: 再打个比方，如果输入是Cat mouse dog rabbit和2,0,1,3，输出也会是dog, cat,
: mouse, rabbit

F*n2016-08-16 07:08

19 楼

public static void invert(String[] strings, int[] indices) {
String tmp = null;
for(int i = 0, n = strings.length; i < n; i++) {
int index = indices[i];
while (index < i) {
index=indices[index];
}
tmp = strings[i];
strings[i] = strings[index];
strings[index]=tmp;
}
}

,0
的1

【在 P****d 的大作中提到】

: 输入是一个字符串数组，一个int数组，输入的字符串数组是另外一个字符串数组通过
: int数组变换得到的，int数组的值代表的是原来这位置上的字符串经过变换后的坐标，
: 然后输出是求变换之前的字符串数组，要求用线性时间，o(1)额外空间
: 打个比方，比如一个字符串数组是"cat", "rabbit","dog", "mouse"，int数组给的2,0
: ,3,1，意思是string数组第0个词是cat，它本来的位置是在哪呢，我们要看int数组，
: int数组的0在index 1上，所以说cat之前应该是1号位的，同理rabbit在string数组的1
: 号位，而index数组3号位的值是1，说明rabbit这个词之前应该在3号位上的，依次类推
: ，所以变换前的字符串数组应该是 dog, cat, mouse, rabbit
: 再打个比方，如果输入是Cat mouse dog rabbit和2,0,1,3，输出也会是dog, cat,
: mouse, rabbit

g*g2016-08-16 07:08

20 楼

解法非线性，循环移位就n^2了

: public static void invert(String[] strings, int[] indices) {

: String tmp = null;

: for(int i = 0, n = strings.length; i

【在 F****n 的大作中提到】

: public static void invert(String[] strings, int[] indices) {
: String tmp = null;
: for(int i = 0, n = strings.length; i < n; i++) {
: int index = indices[i];
: while (index < i) {
: index=indices[index];
: }
: tmp = strings[i];
: strings[i] = strings[index];
: strings[index]=tmp;

s*92016-08-16 07:08

21 楼

这题比较扰，考的是communication的能力，不是编程的能力
楼主想表达的是：
他理解中的转换：
输入：
字符串：［dog, cat, mouse, rabbit, lion, tiger]
数值： [2, 0, 1, 3, 5, 4]
输出：
字符串：［cat, mouse, dog, rabbit tiger, lion]
google的题目：
输入：
字符串：［cat, mouse, dog, rabbit, tiger, lion]
数值： [2, 0, 1, 3, 5, 4]
输出：
字符串：［dog, cat, mouse, rabbit, lion, tiger]
这个其实很简单
搞一个：temp ＝［index, string]
例如 temp ＝［2，dog］
找到2在数值list里的位置0，那么字符串变成
[dog, mouse, dog, rabbit, tiger, lion],
此时 temp ＝［0，cat］
找到0在数值list的位置1，那么字符串变成：
[dog, cat, dog, rabbit, tiger, lion],
temp ＝［1，mouse］
以此类推，要注意的是temp有可能重复，累似如果插入mouse的话，出来的还是［2，
dog］，这时候发现index 0已经有dog了，就可以move到下一个了，也就是［3，rabbit］
题目很简单，楼主被interviewer绕晕了，interviewer肯定表达的也有问题

,0
的1

【在 P****d 的大作中提到】

: 输入是一个字符串数组，一个int数组，输入的字符串数组是另外一个字符串数组通过
: int数组变换得到的，int数组的值代表的是原来这位置上的字符串经过变换后的坐标，
: 然后输出是求变换之前的字符串数组，要求用线性时间，o(1)额外空间
: 打个比方，比如一个字符串数组是"cat", "rabbit","dog", "mouse"，int数组给的2,0
: ,3,1，意思是string数组第0个词是cat，它本来的位置是在哪呢，我们要看int数组，
: int数组的0在index 1上，所以说cat之前应该是1号位的，同理rabbit在string数组的1
: 号位，而index数组3号位的值是1，说明rabbit这个词之前应该在3号位上的，依次类推
: ，所以变换前的字符串数组应该是 dog, cat, mouse, rabbit
: 再打个比方，如果输入是Cat mouse dog rabbit和2,0,1,3，输出也会是dog, cat,
: mouse, rabbit

f*m2016-08-16 07:08

22 楼

人家要求O(n)，你这第二遍循环，找拿到那个index 跟你temp里的index相同时O(n)，
再加上整体的O(n)，你这复杂度O(n^2)，不符合要求。

D*d2016-08-16 07:08

23 楼

解决思路：(a) 由 int[] （记为A) 求逆变换 int[] （记为B), 可以 inplace. (b)
由逆变换 int[] 直接输出变换前的数组。关键在 (a), 遍历一次 A 即可得 B (存在同
一位置). 方法如下:
void GetReverseIndex(int* A, int len) {
if (len <= 0) return;
int count = 0, old = 0;
while (count < len) {
int new = A[old];
int tmp = A[new];
A[new] = old;
old = tmp;
++count;
}
}

m*82016-08-16 07:08

24 楼

桶排序

p*y2016-08-16 07:08

25 楼

我想到一个办法，但是有点作弊的感觉。
假设string 数组Str是:
"cat", "mouse", "dog", "rabbit", "tiger", "lion"
然后顺序数组A是
2， 0， 1， 3， 5， 4
1. 遍历顺序数组。
2. 遍历的时候，比如A[0]=2，那么我们在Str[A[0]]也就是“dog"这个词后面加上“0
”这个数字，并用特殊符号和字符串分开，比如"dog#0".
3. 遍历结束后，所有的字符串中都包含了正向影射时候的序号, 例如
"cat#1", "mouse#2", "dog#0", "rabbit#3", "tiger#5", "lion#6"
4. 这样之后就可以用不停的swap两个元素的方法来做了。
时间复杂度是O(n), 空间O（1）。

,0
的1

【在 P****d 的大作中提到】

: 输入是一个字符串数组，一个int数组，输入的字符串数组是另外一个字符串数组通过
: int数组变换得到的，int数组的值代表的是原来这位置上的字符串经过变换后的坐标，
: 然后输出是求变换之前的字符串数组，要求用线性时间，o(1)额外空间
: 打个比方，比如一个字符串数组是"cat", "rabbit","dog", "mouse"，int数组给的2,0
: ,3,1，意思是string数组第0个词是cat，它本来的位置是在哪呢，我们要看int数组，
: int数组的0在index 1上，所以说cat之前应该是1号位的，同理rabbit在string数组的1
: 号位，而index数组3号位的值是1，说明rabbit这个词之前应该在3号位上的，依次类推
: ，所以变换前的字符串数组应该是 dog, cat, mouse, rabbit
: 再打个比方，如果输入是Cat mouse dog rabbit和2,0,1,3，输出也会是dog, cat,
: mouse, rabbit

y*32016-08-16 07:08

26 楼

楼主已经提到了swap的方法，也说了需要解决cycle的问题。我觉着靠简单地计数来选
择cycle外的下一个坐标行不通，因为cycle外的word可以夹杂在cycle里的word之间。
该怎么做我也没想出好办法。

m*s2016-08-16 07:08

27 楼

1) i=0
IN
Cat mouse dog rabbit
2 0 1 3
OUT
dog mouse cat rabbit
2 0 1 3
swap cat and dog
Leave 2 unchanged, it means find at index 2 for index 0 of original strArray
2) i=1
IN
dog mouse cat rabbit
2 0 1 3
OUT
dog cat mouse rabbit
2 2 1 3
we see intArray[1] = 0 and 0 != i
then intArray[0] tells where to get the string in original strArray
strArray[intArray[1]] = cat
Algo:
if intArray[i] != i do the following
swap strArray[i] and strArray[intArray[i-1]]
always do
let intArray[i] = intArray[i-1]
O(n) time, 0 extra space

p*y2016-08-16 07:08

28 楼

好像这个算法在O（n)里完成不了，每次你在swap之后，需要遍历一边Int[]来找到换到
新位置的那个元素在Int[]的位置。

strArray

【在 m**********s 的大作中提到】

: 1) i=0
: IN
: Cat mouse dog rabbit
: 2 0 1 3
: OUT
: dog mouse cat rabbit
: 2 0 1 3
: swap cat and dog
: Leave 2 unchanged, it means find at index 2 for index 0 of original strArray
: 2) i=1

m*s2016-08-16 07:08

29 楼

没有遍历，每次只是提取intArray[i-1]以及其指向的strArray

【在 p********y 的大作中提到】

: 好像这个算法在O（n)里完成不了，每次你在swap之后，需要遍历一边Int[]来找到换到
: 新位置的那个元素在Int[]的位置。
:
: strArray

s*92016-08-16 07:08

30 楼

因为有个index作为隐形的第三个n space，所以可以交叉引用，再加个‘’ empty
string
复杂度降为O（n）
输入：
字符串：［cat, mouse, dog, rabbit, tiger, lion]
数值： [2, 0, 1, 3, 5, 4]
index： [0, 1, 2, 3, 4, 5]
输出：
字符串：［dog, cat, mouse, rabbit, lion, tiger]
1）
temp ＝ cat
字符串：［dog, mouse, ‘’, rabbit, tiger, lion]
此时字符串[2]为空，查看index2，数值为1，交换
2）
temp ＝ cat
字符串：［dog, ‘’, mouse, rabbit, tiger, lion]
字符串[1]空，查看index1，empty string，跟temp交换
3）
temp ＝‘’
字符串：［dog, cat, mouse, rabbit, tiger, lion]
move到index3，数值为3，不变，下一数值为5，lion存入字符串［4］，temp ＝
tiger
3）
temp ＝ tiger
字符串：［dog, cat, mouse, rabbit,lion,'']
5)
最后swap temp

【在 f*****m 的大作中提到】

: 人家要求O(n)，你这第二遍循环，找拿到那个index 跟你temp里的index相同时O(n)，
: 再加上整体的O(n)，你这复杂度O(n^2)，不符合要求。

s*92016-08-16 07:08

31 楼

原字符串本身可能就包含特殊符号和数字
你在人为的制造bug
千万不能改动原始数据，你这是赤裸裸的等着被拒

“0

【在 p********y 的大作中提到】

: 我想到一个办法，但是有点作弊的感觉。
: 假设string 数组Str是:
: "cat", "mouse", "dog", "rabbit", "tiger", "lion"
: 然后顺序数组A是
: 2， 0， 1， 3， 5， 4
: 1. 遍历顺序数组。
: 2. 遍历的时候，比如A[0]=2，那么我们在Str[A[0]]也就是“dog"这个词后面加上“0
: ”这个数字，并用特殊符号和字符串分开，比如"dog#0".
: 3. 遍历结束后，所有的字符串中都包含了正向影射时候的序号, 例如
: "cat#1", "mouse#2", "dog#0", "rabbit#3", "tiger#5", "lion#6"

w*32016-08-16 07:08

32 楼

当temp为空的时候，怎样知道下一个index该是哪个呢？不会漏掉或重复吗？因为已经
转换过的字符串不能再转换了。
另外，在数值里找任意的数字的复杂度都是O(n)啊，你说的是“找到0在数值list的位
置1”。并不是找index。

【在 s******9 的大作中提到】

: 因为有个index作为隐形的第三个n space，所以可以交叉引用，再加个‘’ empty
: string
: 复杂度降为O（n）
: 输入：
: 字符串：［cat, mouse, dog, rabbit, tiger, lion]
: 数值： [2, 0, 1, 3, 5, 4]
: index： [0, 1, 2, 3, 4, 5]
: 输出：
: 字符串：［dog, cat, mouse, rabbit, lion, tiger]
: 1）

F*n2016-08-16 07:08

33 楼

稍微改一下就行了，把位移后的位置保存
只要循环位移一次，worst 2N not N^2

【在 g*******g 的大作中提到】

: 解法非线性，循环移位就n^2了
:
:
: public static void invert(String[] strings, int[] indices) {
:
: String tmp = null;
:
: for(int i = 0, n = strings.length; i

s*92016-08-16 07:08

34 楼

可能我说的不清楚
temp ＝［index，string］
所以每步你有两个选择
swap 空字符和temp
swap 空字符和字符串中的字符
加一个if语句判断空字符占的index是不是temp中的index，如果是，就用temp中的字符
替代

【在 w****3 的大作中提到】

: 当temp为空的时候，怎样知道下一个index该是哪个呢？不会漏掉或重复吗？因为已经
: 转换过的字符串不能再转换了。
: 另外，在数值里找任意的数字的复杂度都是O(n)啊，你说的是“找到0在数值list的位
: 置1”。并不是找index。

x*22016-08-16 07:08

35 楼

即使原字符串里包含特殊字符也是没有关系的，因为我们始终是加在字符串的后面然后
用一个特殊字符隔开。当记录结束后，我们可以用这些数字替换数字数组里的数字，然
后恢复字符串数组，就可以了。
而且题目的目的就是让你改变输入数据的，不然怎么能用in place的空间解决呢
唯一可能被challenge的地方是，这个方法实际是用了额外的储存空间的。
目前版上的其他方法都没有一个可以真正做到O(n), O(1)的。
楼主可以看leetcode Q289 置顶的解法也是相同思路。

【在 s******9 的大作中提到】

: 原字符串本身可能就包含特殊符号和数字
: 你在人为的制造bug
: 千万不能改动原始数据，你这是赤裸裸的等着被拒
:
: “0

F*n2016-08-16 07:08

36 楼

看我的答案

【在 x******2 的大作中提到】

: 即使原字符串里包含特殊字符也是没有关系的，因为我们始终是加在字符串的后面然后
: 用一个特殊字符隔开。当记录结束后，我们可以用这些数字替换数字数组里的数字，然
: 后恢复字符串数组，就可以了。
: 而且题目的目的就是让你改变输入数据的，不然怎么能用in place的空间解决呢
: 唯一可能被challenge的地方是，这个方法实际是用了额外的储存空间的。
: 目前版上的其他方法都没有一个可以真正做到O(n), O(1)的。
: 楼主可以看leetcode Q289 置顶的解法也是相同思路。

s*92016-08-16 07:08

37 楼

即使不会影响原字符串
你每次还得对字符串进行操作，至少先得辨识最后几位数字，然后cut掉最后的字符串
这个操作很花时间，尤其是字符串很长的话
比方说，你的字符串组含有1billion的 single string（原题没有说string是不是可以
duplicated的）
我可以用1 billion的string，每个string都是字母‘a'
那你要在每个字符串后面加＃再加10位数字来辨识
这样增加的额外空间会很客观，还会远远大于原来的空间
所以，这是个非常吃力不讨好的笨方法
我的方法就是完全的O（n），O（1）

【在 x******2 的大作中提到】

: 即使原字符串里包含特殊字符也是没有关系的，因为我们始终是加在字符串的后面然后
: 用一个特殊字符隔开。当记录结束后，我们可以用这些数字替换数字数组里的数字，然
: 后恢复字符串数组，就可以了。
: 而且题目的目的就是让你改变输入数据的，不然怎么能用in place的空间解决呢
: 唯一可能被challenge的地方是，这个方法实际是用了额外的储存空间的。
: 目前版上的其他方法都没有一个可以真正做到O(n), O(1)的。
: 楼主可以看leetcode Q289 置顶的解法也是相同思路。

n*n2016-08-16 07:08

38 楼

Swap 前面已经提到了；问题上面有人提到了如果有loop怎么办，比如 5，2，1，3，0
，4，7，6的顺序，字符串是什么不重要。

【在 s******9 的大作中提到】

: 即使不会影响原字符串
: 你每次还得对字符串进行操作，至少先得辨识最后几位数字，然后cut掉最后的字符串
: 这个操作很花时间，尤其是字符串很长的话
: 比方说，你的字符串组含有1billion的 single string（原题没有说string是不是可以
: duplicated的）
: 我可以用1 billion的string，每个string都是字母‘a'
: 那你要在每个字符串后面加＃再加10位数字来辨识
: 这样增加的额外空间会很客观，还会远远大于原来的空间
: 所以，这是个非常吃力不讨好的笨方法
: 我的方法就是完全的O（n），O（1）

b*h2016-08-16 07:08

39 楼

So easy, swap and modify int array, whenever swapped, change the
element in the array to be negative.
Starting 0th, and then skipped negative indices to handle next swap until
the end of int array. Two temp variables, one for int array index, one for
temp string

,0
的1

【在 P****d 的大作中提到】

: 输入是一个字符串数组，一个int数组，输入的字符串数组是另外一个字符串数组通过
: int数组变换得到的，int数组的值代表的是原来这位置上的字符串经过变换后的坐标，
: 然后输出是求变换之前的字符串数组，要求用线性时间，o(1)额外空间
: 打个比方，比如一个字符串数组是"cat", "rabbit","dog", "mouse"，int数组给的2,0
: ,3,1，意思是string数组第0个词是cat，它本来的位置是在哪呢，我们要看int数组，
: int数组的0在index 1上，所以说cat之前应该是1号位的，同理rabbit在string数组的1
: 号位，而index数组3号位的值是1，说明rabbit这个词之前应该在3号位上的，依次类推
: ，所以变换前的字符串数组应该是 dog, cat, mouse, rabbit
: 再打个比方，如果输入是Cat mouse dog rabbit和2,0,1,3，输出也会是dog, cat,
: mouse, rabbit

b*h2016-08-16 07:08

40 楼

Check my hints

0

【在 n*******n 的大作中提到】

: Swap 前面已经提到了；问题上面有人提到了如果有loop怎么办，比如 5，2，1，3，0
: ，4，7，6的顺序，字符串是什么不重要。

j*t2016-08-16 07:08

41 楼

How about using unsorted_map, paired with the {number, id}. number
represents the number in the array, id is the position of the number in the
input array. Anyone can tell me what is the complexity of the following
solution? The complexities of both unsorted_map::find and unsorted_map::
insert are O(n).
vector Solution(vector str_list, vector ppos_list)
{
std::unsorted_map table;
vector res;
for(int i =0; i{
table.insert({ppos_list[i], i});
}
res.resize(str_list.size());
for(int i = 0; i{
int j = table.find(i);
res[j] = (str_list[i]);
}
return res;
}

j*t2016-08-16 07:08

42 楼

自顶，哪位高手帮助指点一下我的code能达到要求吗？

the

【在 j******t 的大作中提到】

: How about using unsorted_map, paired with the {number, id}. number
: represents the number in the array, id is the position of the number in the
: input array. Anyone can tell me what is the complexity of the following
: solution? The complexities of both unsorted_map::find and unsorted_map::
: insert are O(n).
: vector Solution(vector str_list, vector ppos_list)
: {
: std::unsorted_map table;
: vector res;
: for(int i =0; i

t*82016-08-16 07:08

43 楼

把你的题翻译一下
一个数组，长度为 n，内部数字为 0， 1， 2，，，， n － 1 随机序列
用 O(n) 时间， O（1） extra space 排序
答案是显然的

,0
的1

【在 P****d 的大作中提到】

: 输入是一个字符串数组，一个int数组，输入的字符串数组是另外一个字符串数组通过
: int数组变换得到的，int数组的值代表的是原来这位置上的字符串经过变换后的坐标，
: 然后输出是求变换之前的字符串数组，要求用线性时间，o(1)额外空间
: 打个比方，比如一个字符串数组是"cat", "rabbit","dog", "mouse"，int数组给的2,0
: ,3,1，意思是string数组第0个词是cat，它本来的位置是在哪呢，我们要看int数组，
: int数组的0在index 1上，所以说cat之前应该是1号位的，同理rabbit在string数组的1
: 号位，而index数组3号位的值是1，说明rabbit这个词之前应该在3号位上的，依次类推
: ，所以变换前的字符串数组应该是 dog, cat, mouse, rabbit
: 再打个比方，如果输入是Cat mouse dog rabbit和2,0,1,3，输出也会是dog, cat,
: mouse, rabbit

d*c2016-08-16 07:08

44 楼

这是置换群
https://en.wikipedia.org/wiki/Permutation_group
楼主用什么cat dog反而复杂化，用单个字母更清楚，另外这里用0 index也实际造成干
扰，分析问题时不应该用。
original: D C M R
int array: 2 0 3 1
input: C R D M
Cauchy's two-line notation:
0 1 2 3
2 0 3 1
求反，https://en.wikipedia.org/wiki/Permutation_group#Neutral_element_and_
inverses
把第二行放到第一行，排序，排序的时候带着自己的同列元素
2 0 3 1 -> 0 1 2 3
0 1 2 3 1 3 0 2
这个就是那个int数组的逆变换，对输入C R D M 用一下就得到输出了
C R D M
0 1 2 3
1 3 0 2
D C M R
总结来说就是排序，排序的时候每个数带着一个尾巴。Cauchy的记法很重要，表达很清
楚。

t*82016-08-16 07:08

45 楼

总共两次排序
每次为 O（n）一个int 临时变量

【在 t**8 的大作中提到】

: 把你的题翻译一下
: 一个数组，长度为 n，内部数字为 0， 1， 2，，，， n － 1 随机序列
: 用 O(n) 时间， O（1） extra space 排序
: 答案是显然的
:
: ,0
: 的1

c*t2016-08-16 07:08

46 楼

题目要求用O(1) space

【在 j******t 的大作中提到】

: 自顶，哪位高手帮助指点一下我的code能达到要求吗？
:
: the

c*t2016-08-16 07:08

47 楼

要对int[] 排序，再对string[] swap, 对吧？
感觉代码有点复杂。
gavinweng 和brfath的解法比较好，直接对String数组swap。

【在 t**8 的大作中提到】

: 总共两次排序
: 每次为 O（n）一个int 临时变量

m*62016-08-16 07:08

48 楼

public static void invert(String[] strings, int[] indices) {
String ts;
for(int i = 0, n = strings.length; i < n; i++) {
int index = indices[i];
if (index != i)
{
// swap string
ts = strings[i];
strings[i] = strings[index];
strings[index] = ts;
// swap index
indices[index] = indices[i];
}
}
}

d*o2016-08-16 07:08

49 楼

乱七八糟写一个
def invert(strs, indices):
for i in range(len(indices)):
index = indices[i]
if index == i:
continue
tmp = strs[index].split(',')
word = tmp[0]
if word:
strs[i] += (',' + word) if strs[i] else word
strs[index] = '' if len(tmp) == 1 else ','.join(tmp[1:])