B*******1
发帖数: 2454 | 1 Given a string having 2n charecters as c1 c3 c5 c7...c2n-1 c2 c4 c6 .....c2n
write an algorithm to rearrange the charecters so that the string will
become as
c1 c2 c3 c4 c5 ......c2n
Max complexity of algo should be O(n)
Do it without using extra storage
这题可以O(n)吗？ |
g*****i
发帖数: 2162 | 2 in place mergesort,应该不可以 |
c*********t
发帖数: 2921 | 3 你在本版看帖不认真。呵呵！
相见
http://www.mitbbs.com/article_t/JobHunting/31935043.html
中 dinohound 的回答。
c2n
【在 B*******1 的大作中提到】
: Given a string having 2n charecters as c1 c3 c5 c7...c2n-1 c2 c4 c6 .....c2n
: write an algorithm to rearrange the charecters so that the string will
: become as
: c1 c2 c3 c4 c5 ......c2n
: Max complexity of algo should be O(n)
: Do it without using extra storage
: 这题可以O(n)吗？
|
f*******t
发帖数: 7549 | 4 前面还有别的帖讨论过，in-place+O(n)不可能
上面提到的dinohound的答案用的是divide-and-conquer，时间复杂度是O(nlogn) |
B*******1
发帖数: 2454 | |
d********y
发帖数: 2114 | 6 it can be done o(n) time and in place.
for each element you can calculate
the right index where you should swap the value.
there was similar question
from ITA. will post code later.
c2n
【在 B*******1 的大作中提到】
: Given a string having 2n charecters as c1 c3 c5 c7...c2n-1 c2 c4 c6 .....c2n
: write an algorithm to rearrange the charecters so that the string will
: become as
: c1 c2 c3 c4 c5 ......c2n
: Max complexity of algo should be O(n)
: Do it without using extra storage
: 这题可以O(n)吗？
|
g**********y
发帖数: 14569 | 7 我想看看你的code, 计算index不难，但是index loop有多个时，我没想到什么好的办法来记住调整过的。
这个code比较ugly, 用计算loop head的办法来判断是否调整：
public String shuffle(String original) {
int N = original.length();
char[] c = original.toCharArray();
for (int i=0; i
if (isLoopHead(i, N)) {
int j = i;
int k = position(j, N);
while (k != i) {
char t = c[i];
c[i] = c[k];
c[k] = t;
j = k;
k = position(j, N);
}
}
}
return new String(c);
}
private int position(int i, int N) {
return i
}
private boolean isLoopHead(int i, int N) {
int j = position(i, N);
while (j != i) {
if (j < i) return false;
j = position(j, N);
}
return true;
}
for each element you can calculate
there was similar question
【在 d********y 的大作中提到】
: it can be done o(n) time and in place.
: for each element you can calculate
: the right index where you should swap the value.
: there was similar question
: from ITA. will post code later.
:
: c2n
|
x******s
发帖数: 398 | 8 就这个问题而言，貌似可以证明只有一个loop吧。能给个两个loop的例子？
in-
【在 g**********y 的大作中提到】
: 我想看看你的code, 计算index不难，但是index loop有多个时，我没想到什么好的办法来记住调整过的。
: 这个code比较ugly, 用计算loop head的办法来判断是否调整：
: public String shuffle(String original) {
: int N = original.length();
: char[] c = original.toCharArray();
: for (int i=0; i: if (isLoopHead(i, N)) {
: int j = i;
: int k = position(j, N);
: while (k != i) {
|
g**********y
发帖数: 14569 | 9 N = 8时，就是两个loop
【在 x******s 的大作中提到】
: 就这个问题而言，貌似可以证明只有一个loop吧。能给个两个loop的例子？
:
: in-
|
x******s
发帖数: 398 | 10 嗯，我之前搞错了一个index.
【在 g**********y 的大作中提到】
: N = 8时，就是两个loop
|
|
|
d********y
发帖数: 2114 | 11 测试了1-20的整数。
class Mix2Array
{
int[] arr;
public bool mix2Array()
{
if (arr == null || arr.Length % 2 != 0)
{
Console.WriteLine("invalid input!");
return false;
}
for (int i = 1; i < arr.Length - 2; i++)
{
int targetIndex = target(i, arr.Length);
while (targetIndex < i)
{
targetIndex = target(targetIndex, arr.Length);
}
if (i != targetIndex)
{
swap(i, targetIndex);
}
printArray();
}
return true;
}
private void swap(int i, int targetIndex)
{
arr[i] ^= arr[targetIndex];
arr[targetIndex] ^= arr[i];
arr[i] ^= arr[targetIndex];
}
private int target(int i, int length)
{
if (i % 2 == 1)
{
return length / 2 + i / 2;
}
else
{
return i / 2;
}
}
}
办法来记住调整过的。
【在 g**********y 的大作中提到】
: 我想看看你的code, 计算index不难，但是index loop有多个时，我没想到什么好的办法来记住调整过的。
: 这个code比较ugly, 用计算loop head的办法来判断是否调整：
: public String shuffle(String original) {
: int N = original.length();
: char[] c = original.toCharArray();
: for (int i=0; i: if (isLoopHead(i, N)) {
: int j = i;
: int k = position(j, N);
: while (k != i) {
|
s******c
发帖数: 1920 | 12 in-place matrix transposition
http://en.wikipedia.org/wiki/In-place_matrix_transposition
c2n
【在 B*******1 的大作中提到】
: Given a string having 2n charecters as c1 c3 c5 c7...c2n-1 c2 c4 c6 .....c2n
: write an algorithm to rearrange the charecters so that the string will
: become as
: c1 c2 c3 c4 c5 ......c2n
: Max complexity of algo should be O(n)
: Do it without using extra storage
: 这题可以O(n)吗？
|
s**x
发帖数: 405 | 13 This can be done in O(n).
I had posted a correct answer about two years ago. |
s**x
发帖数: 405 | 14 My original post seems to have been deleted.
You can find it by google "shyx shuffle" |
g**********y
发帖数: 14569 | 15 这个work, 思路很赞。
【在 d********y 的大作中提到】
: 测试了1-20的整数。
: class Mix2Array
: {
: int[] arr;
: public bool mix2Array()
: {
: if (arr == null || arr.Length % 2 != 0)
: {
: Console.WriteLine("invalid input!");
: return false;
|
s**x
发帖数: 405 | 16 not really. try 1 - 100. there will be failures.
【在 g**********y 的大作中提到】
: 这个work, 思路很赞。
|
B*******1
发帖数: 2454 | 17 本版高人好多啊，careercup那里都是一堆臭老印的烂code，都不如牛人们的短短几行
啊。 |
g**********y
发帖数: 14569 | 18 Are you sure? 我算了N = 2 to 10000，都是对的。从数学上说，我大致可以理解，但
是没想到简单明了的证明。
【在 s**x 的大作中提到】
: not really. try 1 - 100. there will be failures.
|
s**x
发帖数: 405 | 19 Sorry I mis-read the code.
The code from doubleplay is correct.
However, it is not O(n) time. If you don't believe me, try measure it. |
g**********y
发帖数: 14569 | 20 I know, if you count that index calculation as operation, then it's not O(n)
. But I guess in interview, that is not counted. Only swap is counted.
I read your code, it's correct, but too difficult for interview :-)
【在 s**x 的大作中提到】
: Sorry I mis-read the code.
: The code from doubleplay is correct.
: However, it is not O(n) time. If you don't believe me, try measure it.
|
|
|
u**r
发帖数: 663 | 21 我从中间开始交换，假设输入数组存储为a[1...n,n+1...2n]
从a[n],a[n+1]开始，每次把a[n]和a[n+1]交换到正确位置去，直到a[n]=n,a[n+1]=n+1
为止，然后处理a[n-1],a[n+2]，知道最外头，这样每次交换保证两个数位于正确位置
，所以最多交换次数就是n.
大家看看有没有问题？
void main()
{
int n = 20,k,t,tt;
int* c = new int [2*n];
for (int i=0;i<2*n;i++)
{
c[i] = l(i+1,n);
cout<
}
cout<
int idx1 = n, idx2=n+1;
for(idx2=n+1;idx2<=2*n;idx2++,idx1--)
{
while (c[idx2-1] != idx2)
{
t = c[idx2-1];
c[idx2-1] = c[t-1];
c[t-1] = t;
t = c[idx1-1];
c[idx1-1] = c[t-1];
c[t-1] = t;
}
}
for (int i=0;i<2*n;i++)
{
cout<
}
cout<
return;
} |
r*******g
发帖数: 1335 | 22 看不明白，for里面的while存在，怎么还是O(n)的?
【在 d********y 的大作中提到】
: 测试了1-20的整数。
: class Mix2Array
: {
: int[] arr;
: public bool mix2Array()
: {
: if (arr == null || arr.Length % 2 != 0)
: {
: Console.WriteLine("invalid input!");
: return false;
|
u**r
发帖数: 663 | 23 他只计算swap操作，其他的没算。
【在 r*******g 的大作中提到】
: 看不明白，for里面的while存在，怎么还是O(n)的?
|
l*******y
发帖数: 192 | 24 check out here:
http://www.overseatalents.com/node/1880
typical amazon interview questions |
m**q
发帖数: 189 | 25 这个貌似不是O(n)啊
只有在原数组中的数字是有规律的时候，才能保证O(n).
例如原数组为 abcde12345 需要变成a1b2c3d4e5
这时候可以简单的判断数组中的元素是否已经被换到了
它的最终位置。如果没有这个前提的话是这个方法无法保证O(n).
【在 d********y 的大作中提到】
: 测试了1-20的整数。
: class Mix2Array
: {
: int[] arr;
: public bool mix2Array()
: {
: if (arr == null || arr.Length % 2 != 0)
: {
: Console.WriteLine("invalid input!");
: return false;
|
c*****m
发帖数: 315 | 26 double play 的算法真的很妙，可以试用几种不同的SHUFFLE, 只需要换那个TARGET
函数即可。我依葫芦画瓢写了两个:
original array:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
after odd-even shuffle:
1 3 5 7 9 11 13 15 17 19 2 4 6 8 10 12 14 16 18 20
after in-shuffle:
1 11 2 12 3 13 4 14 5 15 6 16 7 17 8 18 9 19 10 20
这个算法看起来有2个LOOP, 但里面那个LOOP 很少RUN， 应该可以证明里面的LOOP 总
数有个UPPER BOUND, 总的时间复杂度很有可能就是O(N)。
public class InShuffle {
public static int target_idx(int idx,int length)
{
int next;
next=2*idx;
if(next>length-1)
next=next-length+1;
return next;
}
public static int target_idx_inshuffle(int idx, int length){
int next;
if(idx%2==1){
next=length/2+idx/2;
}
else
next=idx/2;
return next;
}
public static int [] inshuffle(int [] a){
for(int i=1;i
int next=target_idx_inshuffle(i,a.length);
while(next
next=target_idx_inshuffle(next,a.length);
}
int temp=a[i];
a[i]=a[next];
a[next]=temp;
}
return a;
}
public static int [] shuffle(int [] a){
for(int i=1;i
int next=target_idx(i,a.length);
while(next
next=target_idx(next,a.length);
}
int temp=a[i];
a[i]=a[next];
a[next]=temp;
}
return a;
}
public static void main(String [] args){
int [] a=new int [20];
int [] b;
for(int i=0;i<20;i++){
a[i]=i+1;
}
for(int i=0;i<20;i++){
System.out.print(" ");
System.out.print(a[i]);
}
System.out.println("\n after odd-even shuffle");
b=shuffle(a.clone());
for(int i=0;i<20;i++){
System.out.print(" ");
System.out.print(b[i]);
}
System.out.println("\n after in-shuffle");
b=inshuffle(a.clone());
for(int i=0;i<20;i++){
System.out.print(" ");
System.out.print(b[i]);
}
}
} |
c*****m
发帖数: 315 | |
g***s
发帖数: 30 | 28 int [] rearrange(int [] k) {
if (k == null || k.length < 3)
return k;
int [] n = new int[size_t];
for (int i = 0; i < k.length; i++) {
if (i%2 == 1) {
n[i] = k[i/2];
}
else {
n[i] = k[k.length / 2 + i/2];
}
}
return n;
} |
c*********t
发帖数: 2921 | 29 gloomyturkey,
谢谢你的代码。
我运行了你的代码，非常正确。可是我不太理解它是如何工作的。
我debug了N=12的case,
我发现真正做几乎所有工作的是当index=1的时候，在那个while() 里通过 i, k, swap
值来完成的。对于别的index, isLoopHead 都是false. 当index=0, 和index=11的时候
isLoopHead 返回真，但是不用调整。
你能不能通俗易懂的说说你的logic?
isLoopHead()到底是想做什么？为什么isLoopHead（）本身还有一个while()?它的物理
含义是什么？
你所谓的"loop"到底是代表什么？ loop head指的又是什么？
position()好理解，是得到应该的位置。
办法来记住调整过的。
【在 g**********y 的大作中提到】
: 我想看看你的code, 计算index不难，但是index loop有多个时，我没想到什么好的办法来记住调整过的。
: 这个code比较ugly, 用计算loop head的办法来判断是否调整：
: public String shuffle(String original) {
: int N = original.length();
: char[] c = original.toCharArray();
: for (int i=0; i: if (isLoopHead(i, N)) {
: int j = i;
: int k = position(j, N);
: while (k != i) {
|
g**********y
发帖数: 14569 | 30 你看doubleplay的code吧，更有效率。我的code处理方式是：对一个loop, 依次交换，
但是这个交换只在loopHead的位置进行，也就是index最小的地方。
doubleplay的code是：反向交换，每次把正确值调整到位置i。正确值位置大于i, 直接
调整；小于i, 说明该值已经被挪到下一个位置，循环找，找到后(也就是pos > i)时，
调整。
shyx有更进一步的解释和code, 见：http://fayaa.com/code/view/612/
swap
【在 c*********t 的大作中提到】
: gloomyturkey,
: 谢谢你的代码。
: 我运行了你的代码，非常正确。可是我不太理解它是如何工作的。
: 我debug了N=12的case,
: 我发现真正做几乎所有工作的是当index=1的时候，在那个while() 里通过 i, k, swap
: 值来完成的。对于别的index, isLoopHead 都是false. 当index=0, 和index=11的时候
: isLoopHead 返回真，但是不用调整。
: 你能不能通俗易懂的说说你的logic?
: isLoopHead()到底是想做什么？为什么isLoopHead（）本身还有一个while()?它的物理
: 含义是什么？
|
|
|
w****x
发帖数: 2483 | 31 int ClacTarget(int nLen, int nIndex)
{
assert(nLen > 0 && nIndex > 0 && nLen > nIndex);
if (nIndex < nLen/2)
return 2 * nIndex;
return (nIndex - nLen/2) * 2 + 1;
}
char* InplaceConvert(char* str)
{
if (NULL == str)
return NULL;
int nLen = strlen(str);
if (0 == nLen || nLen%2 != 0)
return str;
int nCount = nLen - 2;
for (int i = 1; i < nLen && nCount > 0; i += 2)
{
int nCur = ClacTarget(nLen, i);
char cTmp = str[nCur];
str[nCur] = str[i];
nCount--;
while (nCur != i)
{
nCur = ClacTarget(nLen, nCur);
char c = str[nCur];
str[nCur] = cTmp;
cTmp = c;
nCount--;
}
}
return str;
} |
H*X
发帖数: 281 | 32 也写了一下, a是数组指针, n 是数组大小,
没有计算index, 直接就是从左到右扫描, 如果a[i]的数值不对就一直swap,一直到a[i]
=i+1.
计算了一下, 如果array length是100000的话, while()循环里面的指令被执行了99796
次,对比了一下之前doubleplay的算法, 他的swap()也是执行了99796次, 不过他的
while()循环里面被执行了552860次.
void re_order(int* a, int n)
{
int i,j,k;
for (i = 1; i
while (a[i] != i+1) {
k = a[i];
j = a[k -1];
a[k-1] = k;
a[i] = j;
}
}
} |
r*******g
发帖数: 1335 | 33 我比较了你和doubleplay的算法，然后自己用二分法写了个，二分法的效率是O(nlogn)
我现在还没看懂doubleplay的算法，你的算法更容易理解，每次判断是否是loop的开头
，doubleplay那个至今理解不了。
但是我发觉你们的结果都没有二分法快啊，我用的N=10000000，你能不能测试下，不知
道结果是不是和我类似，难道是c++的问题？
感觉你们这个也不是O(N)，shyx那个是O(N)，但是很难想到什么基于素数的算法。
void Swap(int * array,int begin,int end){
for (int i=0;i<(end-begin+1)/2;i++){
int tmp=array[begin+i];
array[begin+i]=array[end-i];
array[end-i]=tmp;
}
}
void Convert(int * array,int begin,int total){
int N=total/2;
if(N==1)
return;
if(N==2){
Swap(array,begin+1,begin+2);
return;
}
int middle=N/2;
//a b -> b a. a: begin+middle to begin+N-1, b: begin+N to begin+N+
middle-1
Swap(array, begin+middle,begin+N-1);
Swap(array, begin+N,begin+N+middle-1);
Swap(array, begin+middle, begin+N+middle-1);
Convert(array, begin, (middle)*2);
Convert(array, begin+(middle)*2, (N-middle)*2);
}
【在 g**********y 的大作中提到】
: 你看doubleplay的code吧，更有效率。我的code处理方式是：对一个loop, 依次交换，
: 但是这个交换只在loopHead的位置进行，也就是index最小的地方。
: doubleplay的code是：反向交换，每次把正确值调整到位置i。正确值位置大于i, 直接
: 调整；小于i, 说明该值已经被挪到下一个位置，循环找，找到后(也就是pos > i)时，
: 调整。
: shyx有更进一步的解释和code, 见：http://fayaa.com/code/view/612/
:
: swap
|
C*******l
发帖数: 1198 | 34 大家都是数学王啊，都用这么专业的字眼。
你那个extra storage是指连几个数字或几个pointer都不给用还是可以用几个呢？如果
准用3个格子 O(n) 很简单。我不懂多少，就insertion。O(n) time O(1) storage
overhead。 |
C*******l
发帖数: 1198 | 35 怎么说都好了，阁下是好人。
http://fayaa.com/code/view/612/raw/
【在 s**x 的大作中提到】
: Sorry I mis-read the code.
: The code from doubleplay is correct.
: However, it is not O(n) time. If you don't believe me, try measure it.
|
