y******x
发帖数: 31 | 1 given int array A, R, permute A to make output array O as O[R[i]]=A[i]
e.g A={1,2,3}, R={1,2,0}=> O{3,1,2}
O(1) space 怎么做？ | l**o
发帖数: 356 | 2 直接用他给的那个公式往O里填数不就可以了？还是我想得简单了？ | d**********6
发帖数: 4434 | 3 只要求O(1) space没要求时间吗？
这好办
for(i=0; i
for(j=0; j
if(R[j] == i){
print A[j]
}
}
} | m*****g
发帖数: 71 | 4 for ( int i = 0; i < R.length; ++i) {
O[R[i]] = A[i];
}
这样行不？前提是R、A、O等长，R里不能有超界的值，不能有重复什么的无效情况。 | d**********6
发帖数: 4434 | 5 要allocate O, 就不是O(1)了吧
【在 m*****g 的大作中提到】
: for ( int i = 0; i < R.length; ++i) {
: O[R[i]] = A[i];
: }
: 这样行不？前提是R、A、O等长，R里不能有超界的值，不能有重复什么的无效情况。
| l**o
发帖数: 356 | 6 好像我理解错了，是在原A上改？
可以对Bsort，B中元素怎么换位置，A中相应的也怎么换？ | b**********5
发帖数: 7881 | 7 这个print， 也太cheating了。 如果function是
sort（int[] A, int[] R), and after the function, A will be the result of the
new sorted array, what would u do?
【在 d**********6 的大作中提到】
: 只要求O(1) space没要求时间吗？
: 这好办
: for(i=0; i: for(j=0; j: if(R[j] == i){
: print A[j]
: }
: }
: }
| y******x
发帖数: 31 | 8 这个不对吧，要print 3 1 2
【在 d**********6 的大作中提到】
: 只要求O(1) space没要求时间吗？
: 这好办
: for(i=0; i: for(j=0; j: if(R[j] == i){
: print A[j]
: }
: }
: }
| c*****y
发帖数: 27 | 9 就是说R是0:n的一个permutation， 然后你要在A上面实现这个permutation， 不能用
其他空间。
想把R拆了，然后做轮换(要多申请几个变量，O(1)space)。但是应该有更简单方法。 | a****r
发帖数: 87 | 10 这个可以通过swap来实现。最坏情况下需要swap n 次. we can keep a counter, if
the current position does not need to swap, then increase the counter by one
. if it needs swap, we can swap once, but this swap will make sure that
destination position will not be swapped again, then at least one element is
fixed.
void swapArray(vector &A, vector &R, int i, int j){
swap(A[i], A[j]);
swap(R[i], R[j]);
}
void inPlacePermutation(vector &A, vector &R){
int cnt = 0;
int i = 0;
while (cnt < A.size()) {
if(R[i] == i) {
cnt++;
i++;
}else{
swapArray(A, R, i, R[i]);
cnt;
}
}
return;
} | | | m*****g
发帖数: 71 | 11 n^2方案，大家看看有问题没？
public static boolean permute(int[] A, int[] R) {
if (A.length != R.length) {
System.out.println("Wrong input!");
return false;
}
int i = 0;
int j = 0;
int temp = A[0];
while (true) {
j = find(R, i);
if (j == 0) {
A[i] = temp;
break;
} else if (j > 0 && j < A.length){
A[i] = A[j];
i = j;
} else {
System.out.println("Wrong input!");
break;
}
}
return true;
}
//find i in R[], return index
private static int find(int[] R, int i) {
for (int j = 0; j < R.length; ++j) {
if (R[j] == i) {
return j;
}
}
return -1;
} | U***A
发帖数: 849 | 12 可以O(n)?
这样可以吗？
void permuteAR(vector &A, vector &R){
int size = (int)A.size();
if(size <=1) return;
int count = 0;
int i = 0;
int tmp = A[0];
while(count
int tmp1 = A[R[i]];
A[R[i]] = tmp;
count++;
tmp = tmp1;
i = R[i];
}
} | x**********g
发帖数: 44 | 13 对R里面的元素排序，同时更新A里面的元素顺序，最后按顺序输出A，不知道这样算不
算O（1）？
for(i=1; i
for(j=i; j>0; j--){
if(R[j-1]>R[j]){
tempR==R[j]; tempA=A[j];
R[j]=R[j-1]; A[j]=A[j-1];
R[j-1]=tempR; A[j-1]=tempA;
}
else break;
}
}
更新后的 A其实就是想要的 O了
时间复杂度和排序是一样的，可以优化
要求 R里面的元素一定是 0,1,2,...,n,然后 A.length>=R.length，否则要输出null之类
如果 R不是0到n，的话，比如{1,3,5,2,8}，那么更新后的R为{1,2,3,5,8}
for（i=0，i
print(A[R[i]]);
} | j**7
发帖数: 143 | 14 public static int[] permute(int[] A, int[] R) {
for (int i = 0; i < A.length; i++) {
while (R[i] != i) {
int temp = A[i];
A[i] = A[R[i]];
A[R[i]] = temp;
temp = R[R[i]];
R[R[i]] = R[i];
R[i] = temp;
}
}
return A;
} | x**********g
发帖数: 44 | 15 这样不行吧，只能在一个圈里面转哟
如果R={3,0,2,1,5,4}, i=0开始就只能在 3,0,1里面转哟
【在 U***A 的大作中提到】
: 可以O(n)?
: 这样可以吗？
: void permuteAR(vector &A, vector &R){
: int size = (int)A.size();
: if(size <=1) return;
:
: int count = 0;
: int i = 0;
: int tmp = A[0];
: while(count
| d**********6
发帖数: 4434 | 16 你跟10楼的思路一样，不过他是selection sort，你是bubble sort
看来还可以做insert sort了
【在 x**********g 的大作中提到】
: 对R里面的元素排序，同时更新A里面的元素顺序，最后按顺序输出A，不知道这样算不
: 算O（1）？
: for(i=1; i: for(j=i; j>0; j--){
: if(R[j-1]>R[j]){
: tempR==R[j]; tempA=A[j];
: R[j]=R[j-1]; A[j]=A[j-1];
: R[j-1]=tempR; A[j-1]=tempA;
: }
: else break;
| x**********g
发帖数: 44 | 17 这个赞！针对R是0:n的情况很好使
【在 j**7 的大作中提到】
: public static int[] permute(int[] A, int[] R) {
: for (int i = 0; i < A.length; i++) {
: while (R[i] != i) {
: int temp = A[i];
: A[i] = A[R[i]];
: A[R[i]] = temp;
: temp = R[R[i]];
: R[R[i]] = R[i];
: R[i] = temp;
: }
| r*****t
发帖数: 68 | 18 How about this?
i:place holder of A[j]
j:next one that need swap
int n=A.size();
for(int i=0, j=0;n>0;n--)
{
if(i>=R[j])//i=R[i] need not swap; i>R[j]: swapped before
{
i++;
j=i;
}
else
{
swap(A[i],A[R[j]]);
j=R[j];
}
}
【在 y******x 的大作中提到】
: given int array A, R, permute A to make output array O as O[R[i]]=A[i]
: e.g A={1,2,3}, R={1,2,0}=> O{3,1,2}
: O(1) space 怎么做？
| r***d
发帖数: 79 | 19 是否可以像矩阵原地转置那样，分别处理每一个局部轮换，这样可以只用O(1) space，
然后注意判断是否为已经处理过的同一局部轮换
given int array A, R, permute A to make output array O as O[R[i]]=A[i]
e.g A={1,2,3}, R={1,2,0}=> O{3,1,2}
O(1) space 怎么做？
【在 y******x 的大作中提到】
: given int array A, R, permute A to make output array O as O[R[i]]=A[i]
: e.g A={1,2,3}, R={1,2,0}=> O{3,1,2}
: O(1) space 怎么做？
| b***e
发帖数: 1419 | 20 This works but is not the best. The problem is that
R[i] = temp
is completely unnecessary. You can actually leave the value in temp and
simply check
temp == i
each loop. This way you could save around 30% linear time. If I were the
interviewer that would be part of what I were looking for.
【在 j**7 的大作中提到】
: public static int[] permute(int[] A, int[] R) {
: for (int i = 0; i < A.length; i++) {
: while (R[i] != i) {
: int temp = A[i];
: A[i] = A[R[i]];
: A[R[i]] = temp;
: temp = R[R[i]];
: R[R[i]] = R[i];
: R[i] = temp;
: }
| | | j**7
发帖数: 143 | 21 Could you provide your complete solution?
Thanks
the
【在 b***e 的大作中提到】
: This works but is not the best. The problem is that
: R[i] = temp
: is completely unnecessary. You can actually leave the value in temp and
: simply check
: temp == i
: each loop. This way you could save around 30% linear time. If I were the
: interviewer that would be part of what I were looking for.
| r****7
发帖数: 2282 | 22 这个不就是LC的题改得么
void permute(vector &r, vector &a)
{
int sz = r.size();
for (int i = 0; i < sz; i ++) {
while (r[i] != i) {
int tmp = r[r[i]];
int tmp2 = a[r[i]];
a[r[i]] = a[i];
r[r[i]] = r[i];
r[i] = tmp;
a[i] = tmp2;
}
}
}
【在 y******x 的大作中提到】
: given int array A, R, permute A to make output array O as O[R[i]]=A[i]
: e.g A={1,2,3}, R={1,2,0}=> O{3,1,2}
: O(1) space 怎么做？
| r****7
发帖数: 2282 | 23 没听懂，他的解法和我的一样
不给R[i]赋值的话后边会被覆盖掉
the
【在 b***e 的大作中提到】
: This works but is not the best. The problem is that
: R[i] = temp
: is completely unnecessary. You can actually leave the value in temp and
: simply check
: temp == i
: each loop. This way you could save around 30% linear time. If I were the
: interviewer that would be part of what I were looking for.
| d******e
发帖数: 2265 | 24 2n worst time
def swapandlabel(l, r, i, j):
''' swap array and label ratation.'''
tmp = l[i]
l[i] = l[j]
l[j] = tmp
r[i] = r[j]
r[j] = j
def shuffle(l, r):
for i in range(len(r)):
while r[i] != i:
swapandlabel(l, r, i, r[index])
【在 j**7 的大作中提到】
: Could you provide your complete solution?
: Thanks
:
: the
| v********o
发帖数: 67 | 25 这个swapandlabel函数值传递j = r[index]干的不就是人家temp = R[R[i]]的事么？
把函数扩展出来就是一样的了吧。。。
【在 d******e 的大作中提到】
: 2n worst time
: def swapandlabel(l, r, i, j):
: ''' swap array and label ratation.'''
: tmp = l[i]
: l[i] = l[j]
: l[j] = tmp
: r[i] = r[j]
: r[j] = j
: def shuffle(l, r):
: for i in range(len(r)):
| b***e
发帖数: 1419 | 26 /* Save an assignment for each loop */
public static void permute(int[] R) {
for (int i = 0; i < R.length; i++) {
while (R[i] == i) { i++; }
int j = i;
int buffer;
while (R[j] != i) {
int t = R[R[j]];
buffer = A[R[j]];
R[R[j]] = R[j];
A[R[j]] = A[j];
j = t;
}
R[i] = i;
A[i] = buffer;
}
}
【在 j**7 的大作中提到】
: Could you provide your complete solution?
: Thanks
:
: the
|
|
