等了一个月，FIA终于到手，真是慢啊。。。 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Money - 海外理财

等了一个月，FIA终于到手，真是慢啊。。。

等了一个月，FIA终于到手，真是慢啊。。。# Money - 海外理财

s*n2013-07-11 07:07

1 楼

0 1 2 3 4 5 6 7 (N=8, k=3)
->
3 4 5 6 7 0 1 2
leetcode上那个要移动2N次，写了个只要移动N次的
#include
void rotate(int* a, int N, int k)
{
if (N<=1) return;
if (k>N) k=k%N;
if (k==0) return;
int moved = 0;
for (int i=0; movedint tmp = a[i];
int current = i;
do {
moved++;
int next = (current+k)%N;
if (next == i) {
a[current] = tmp;
break;
} else {
a[current] = a[next];
current = next;
}
} while (1);
}
}
int main()
{
int a[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
rotate(a, 10, 7);
for (int i=0; i<10; i++) printf("%d ", a[i]);
}

A*l2013-07-11 07:07

2 楼

才2500CL，今天随便买点日用品就500没了，哪里够用。。。
那天小二问我要不要从BOA转CL过来我脑子进水没答应。。。
另外，FIA通过Google Wallet给别人email钱算purchase么？

p*22013-07-11 07:07

3 楼

注意k可以为负数

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

: 0 1 2 3 4 5 6 7 (N=8, k=3)
: ->
: 3 4 5 6 7 0 1 2
: leetcode上那个要移动2N次，写了个只要移动N次的
: #include
: void rotate(int* a, int N, int k)
: {
: if (N<=1) return;
: if (k>N) k=k%N;
: if (k==0) return;

w*x2013-07-11 07:07

4 楼

我只想问你是不是cleverman, wahaha

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

:
: 注意k可以为负数

w*o2013-07-11 07:07

5 楼

这个太牛了。
研究了半天终于明白了。
就是按照每次k步的跳去 copy,会形成一个环，
如果还没有把所有的copy完，
然后开始下一个环，
直到拷贝了N次。

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

l*82013-07-11 07:07

6 楼

if ( k<0 )
k += N;

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

:
: 注意k可以为负数

l*82013-07-11 07:07

7 楼

Nice, I think it works.

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

w*y2013-07-11 07:07

8 楼

我昨天刚研究了这个题目, 别人跟我说programming pearl上有, 我看了半天看懂了
juggling怎么做, 但是不太懂怎么证明orz
Juggling的方法, 如果gcd(N,k)是1, 我看的很晕, 如果gcd(N,k)大于一, 因为可以画
出图来, 我就想的明白

c*t2013-07-11 07:07

9 楼

woomy,
能说说programming pearl上哪里讲这题了吗？
什么是juggling?
哪里有什么link?
谢谢！

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

: 我昨天刚研究了这个题目, 别人跟我说programming pearl上有, 我看了半天看懂了
: juggling怎么做, 但是不太懂怎么证明orz
: Juggling的方法, 如果gcd(N,k)是1, 我看的很晕, 如果gcd(N,k)大于一, 因为可以画
: 出图来, 我就想的明白

l*82013-07-11 07:07

10 楼

稍微改了一下 swanswan的程序：
void rotate(int* a, int N, int k)
{
if (N<=1) return;
k=（k%N + N) % N ;
if (k==0) return;
int gcdNK = gcd(N, k); // greatest common divisor
for (int i=0; iint tmp = a[i];
int current;
int next = i;
do {
current = next;
next = (current+k)%N;
a[current] = a[next];
} while (next != i);
a[current] = tmp;
}
}

m*g2013-07-11 07:07

11 楼

O(n) 的解法：
array = {1, 2, 4, 5, 6, 7, 9, 12}, k = 3，length = 8
1. 先reverse 前面 5个数 {1，2， 4，5，6} －－>｛6, 5,4,2,1｝(length - k)/2
2. 再reverse 后面3个数｛7，9，12｝－－> {12, 9, 7} k/2
现在的array ＝｛6， 5， 4，2，1， 12， 9，7｝
3. 现在把整个array reverse ＝｛7 9 12 1 2 4 5 6 ｝length/2
所以total runtime ＝（length -k ）/2 + k/2 + length/2 = length
code:
==========
private static void rotate(int[] array, int k)
{
int length = array.length;

k = (k % length + length) % length;

for(int i = 0, j = length -k -1; i< j; i++, j--)
{
swap(array, i, j);
}

for(int i = length - k, j = length -1; i< j; i++, j--)
{
swap(array, i, j);
}

for(int i = 0, j = length - 1; i < j; i++, j--)
{
swap(array, i, j);
}
}
private static void swap(int[] array, int i, int j)
{
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
==========

l*82013-07-11 07:07

12 楼

Another method (Block swap algorithm for array rotation):
void swapBlock(int a[], int block1, int block2, int blockSize)
{
int block1End = block1 + blockSize;
while (block1 < block1End) {
int tmp = a[block1];
a[block1++] = a[block2];
a[block2++] = tmp;
}
}
void leftRotate(int a[], size_t N, int k)
{
if (N<2) return;
k = (k%N + N) % N;
if (k == 0) return;
int start = 0; // start index of unprocessed array
int end = N; // end index of unprocessed array
int leftK = k; // rotate to left by leftK elements
int rightK = N-k; // or rotate to right by rightK elements
while (leftK != rightK) {
if ( leftK < rightK ) { // left rotation is better
swapBlock(a, start, end-leftK, leftK);
end -= leftK; // change border because the right-most leftK contains final numbers
rightK -= leftK;
}

if ( leftK > rightK ) { // equivalent right rotation is better
swapBlock(a, start, end-rightK, rightK);
start += rightK;
leftK -= rightK;
}
}
swapBlock(a, start, end-leftK, leftK);
}

g*u2013-07-11 07:07

13 楼

这个是不是更好理解一点
void myrotate(int* a, int N, int k)
{
if (N<=1) return;
if (k>N) k=k%N;
if (k==0) return;
int currentIndex,nextIndex;
int currentValue,nextValue;
currentIndex = 0;
currentValue=a[currentIndex];
for (int i=0; inextIndex=(currentIndex+N-k)%N;
nextValue=a[nextIndex];
a[nextIndex]=currentValue;
currentIndex=nextIndex;
currentValue=nextValue;
}
}

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

l*82013-07-11 07:07

14 楼

this doesn't work when N=4, k=2.
Try it. I think you'll get original array as your result.

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

: 这个是不是更好理解一点
: void myrotate(int* a, int N, int k)
: {
: if (N<=1) return;
: if (k>N) k=k%N;
: if (k==0) return;
: int currentIndex,nextIndex;
: int currentValue,nextValue;
: currentIndex = 0;
: currentValue=a[currentIndex];

g*u2013-07-11 07:07

15 楼

You are right, it failed. The output is weird, it's 1 2 1 4. The problem is
only two positions are exchanging elements.
Thanks! :)

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

: this doesn't work when N=4, k=2.
: Try it. I think you'll get original array as your result.

l*82013-07-11 07:07

16 楼

you're welcome. in swan's code, i is the start of a chain. When one chain
is finished but not all the elements are moved, start the next chain.

is

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

: You are right, it failed. The output is weird, it's 1 2 1 4. The problem is
: only two positions are exchanging elements.
: Thanks! :)

g*u2013-07-11 07:07

17 楼

Yes, got it.
Here is the revised one, it works. Now it's almost same as swan's.
void myrotate(int* a, int N, int k)
{
if (N<=1) return;
if (k>N) k=k%N;
if (k==0) return;
int currentIndex,nextIndex;
int currentValue,nextValue;
int numMove=0;
int startIndex;
for (int i=0; numMovestartIndex=i;
currentIndex = i;
currentValue=a[currentIndex];
while(1){
numMove++;
nextIndex=(currentIndex+N-k)%N;
nextValue=a[nextIndex];
a[nextIndex]=currentValue;
currentIndex=nextIndex;
currentValue=nextValue;
if(currentIndex==startIndex)
break;
}
}
}

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

: you're welcome. in swan's code, i is the start of a chain. When one chain
: is finished but not all the elements are moved, start the next chain.
:
: is

r*b2013-07-11 07:07

18 楼

This algorithm requires N divisions. Is this really more efficient than
leetcode's algo?

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

l*82013-07-11 07:07

19 楼

int next = (current+k)%N;
can be replaced by:
int next = current+k;
if (next>N)
next -= N;
And you're right, for integer array, this algorithm is not necessarily
faster than leetcode's algorithm.
But I think it's faster for object array because it needs less object move.

【在 r*****b 的大作中提到】

: This algorithm requires N divisions. Is this really more efficient than
: leetcode's algo?

w*y2013-07-11 07:07

20 楼

http://www.geeksforgeeks.org/archives/2398
这里面的method 3

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

: woomy,
: 能说说programming pearl上哪里讲这题了吗？
: 什么是juggling?
: 哪里有什么link?
: 谢谢！

w*x2013-07-11 07:07

21 楼

问题是一次pass也不一定快啊,取模开销太大了

l*82013-07-11 07:07

22 楼

int next = (current+k)%N;
can be replaced by:
int next = current+k;
if (next>N)
next -= N;
这个开销小些吧？

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

: 问题是一次pass也不一定快啊,取模开销太大了

l*82013-07-11 07:07

23 楼

不需要取模的。
c++ stl 源代码里面就是用的juggling算法做array rotating.

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

: 问题是一次pass也不一定快啊,取模开销太大了

a*n2013-07-11 07:07

24 楼

programming pearl 上的原题