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
|
|