s******n
发帖数: 3946 | 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; moved
int 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]);
} | p*****2
发帖数: 21240 | 2
注意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****x
发帖数: 2483 | 3
我只想问你是不是cleverman, wahaha
【在 p*****2 的大作中提到】
:
: 注意k可以为负数
| w****o
发帖数: 2260 | 4 这个太牛了。
研究了半天终于明白了。
就是按照每次k步的跳去 copy,会形成一个环，
如果还没有把所有的copy完，
然后开始下一个环，
直到拷贝了N次。
【在 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;
| l*********8
发帖数: 4642 | 5 if ( k<0 )
k += N;
【在 p*****2 的大作中提到】
:
: 注意k可以为负数
| l*********8
发帖数: 4642 | 6 Nice, I think it works.
【在 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***y
发帖数: 6251 | 7 我昨天刚研究了这个题目, 别人跟我说programming pearl上有, 我看了半天看懂了
juggling怎么做, 但是不太懂怎么证明orz
Juggling的方法, 如果gcd(N,k)是1, 我看的很晕, 如果gcd(N,k)大于一, 因为可以画
出图来, 我就想的明白 | c*********t
发帖数: 2921 | 8 woomy,
能说说programming pearl上哪里讲这题了吗？
什么是juggling?
哪里有什么link?
谢谢！
【在 w***y 的大作中提到】
: 我昨天刚研究了这个题目, 别人跟我说programming pearl上有, 我看了半天看懂了
: juggling怎么做, 但是不太懂怎么证明orz
: Juggling的方法, 如果gcd(N,k)是1, 我看的很晕, 如果gcd(N,k)大于一, 因为可以画
: 出图来, 我就想的明白
| l*********8
发帖数: 4642 | 9 稍微改了一下 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; i
int 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********g
发帖数: 272 | 10 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*********8
发帖数: 4642 | 11 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**u
发帖数: 504 | 12 这个是不是更好理解一点
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; i
nextIndex=(currentIndex+N-k)%N;
nextValue=a[nextIndex];
a[nextIndex]=currentValue;
currentIndex=nextIndex;
currentValue=nextValue;
}
}
【在 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;
| l*********8
发帖数: 4642 | 13 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**u
发帖数: 504 | 14 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*********8
发帖数: 4642 | 15 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**u
发帖数: 504 | 16 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; numMove
startIndex=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*****b
发帖数: 310 | 17 This algorithm requires N divisions. Is this really more efficient than
leetcode's algo?
【在 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;
| l*********8
发帖数: 4642 | 18 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***y
发帖数: 6251 | 19 http://www.geeksforgeeks.org/archives/2398
这里面的method 3
【在 c*********t 的大作中提到】
: woomy,
: 能说说programming pearl上哪里讲这题了吗？
: 什么是juggling?
: 哪里有什么link?
: 谢谢！
| w****x
发帖数: 2483 | 20 问题是一次pass也不一定快啊,取模开销太大了 | | | l*********8
发帖数: 4642 | 21 int next = (current+k)%N;
can be replaced by:
int next = current+k;
if (next>N)
next -= N;
这个开销小些吧？
【在 w****x 的大作中提到】
: 问题是一次pass也不一定快啊,取模开销太大了
| l*********8
发帖数: 4642 | 22 不需要取模的。
c++ stl 源代码里面就是用的juggling算法做array rotating.
【在 w****x 的大作中提到】
: 问题是一次pass也不一定快啊,取模开销太大了
| a****n
发帖数: 1887 | |
|
