由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - Rotating an array in place
相关主题
问大家关于编程的经验Google店面
amazon 电面题binary search in rotated sorted array有重复时怎么办?
find longest subarray with the equal number of 0's, 1's这个rotated sorted array问题
MS Onsite面经问个rotated array里面找element的问题
小结可以应用二分查找的面试题问一道CareerCup里的题目
leetcode里面的rotate array的[1,2], 3是什么意思?再问一个算法题。
一题貌似在AMAZON和MICROSOFT都出现过的题目。search in a rotated array
write a c++ code for rotated sorted array问一个search in rotated array的问题
相关话题的讨论汇总
话题: int话题: array话题: nextindex话题: leftk
进入JobHunting版参与讨论
1 (共1页)
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;
}
==========
相关主题
leetcode里面的rotate array的[1,2], 3是什么意思?Google店面
一题貌似在AMAZON和MICROSOFT都出现过的题目。binary search in rotated sorted array有重复时怎么办?
write a c++ code for rotated sorted array这个rotated sorted array问题
进入JobHunting版参与讨论
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也不一定快啊,取模开销太大了
相关主题
问个rotated array里面找element的问题search in a rotated array
问一道CareerCup里的题目问一个search in rotated array的问题
再问一个算法题。把leetcode做完了
进入JobHunting版参与讨论
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
23
programming pearl 上的原题
1 (共1页)
进入JobHunting版参与讨论
相关主题
问一个search in rotated array的问题小结可以应用二分查找的面试题
把leetcode做完了leetcode里面的rotate array的[1,2], 3是什么意思?
lc新题,贴个刚写的solution一题貌似在AMAZON和MICROSOFT都出现过的题目。
Leetcode上面的"Search in rotated sorted array II"write a c++ code for rotated sorted array
问大家关于编程的经验Google店面
amazon 电面题binary search in rotated sorted array有重复时怎么办?
find longest subarray with the equal number of 0's, 1's这个rotated sorted array问题
MS Onsite面经问个rotated array里面找element的问题
相关话题的讨论汇总
话题: int话题: array话题: nextindex话题: leftk