Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit520f505

Browse files
committed
Create RotateArray.java
The code is to solve the problem of rotating an array in place. The problem states as: Rotate an array of n elements to the right by k steps. For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].The idea is move every item to its desired location at once, that is, we move `i` to `i+k` for all `L` possible `i`'s where `L = nums.length`. To handle the case of overshooting, `i+k` is indeed `(i+k)%L`. We start with `i=0` as the first round. It is for sure that after several steps, we have `i>=L`, meaning we have done with one round. For the next round, `i` will start from `i%L`. But hold on, we need to handle one special case, that is when `i%L == 0` (meaning that after moving for one round `i` gets to its starting point). We need to handle this case to avoid infinite loops. This is handled in the `if` loop in the code. That is, whenever this happens, we simply move `i` to its next location, i.e., `i=i+1`. And we also need a variable that stores previous `i`, which is `starti` in the code. We use a `counter` to counter the number of items already moved and stops moving when `counter==L`, i.e., all items are done moving.I will give a simple example of how the idea works with the following array of length 5: [1, 2, 3, 4, 5]Suppose `k=3`. `i` starts from `0`: - `current`=0, and `next`=(current+3)%5=3, thus, 4 is replaced with 1 (or 1 is moved to the location of 4). Array becomes: [1, 2, 3, 1, 5] - `current`=3, and `next`=(current+3)%5=1, thus 2 is replaced with 4. Array becomes: [1, 4, 3, 1, 5] - `current`=1 and `next`=(1+3)%5=4, thus 5 is replaced with 2. Array becomes: [1, 4, 3, 1, 2] - `current`=4 and `next`=(4+3)%5=2, thus 3 is replaced with 5. Array becomes: [1, 4, 5, 1, 2] - `current`=2 and `next`=(2+3)%5=0, thus 1 is replaced with 3. Array becomes: [3, 4, 5, 1, 2]And we are done!
1 parent479a42f commit520f505

File tree

1 file changed

+32
-0
lines changed

1 file changed

+32
-0
lines changed

‎Math/RotateArray.java

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
publicclassRotateArray {
2+
publicvoidrotate(int[]nums,intk) {
3+
intL=nums.length,counter=0,currentLoc=0,starti=0,prevVal=nums[currentLoc];
4+
k =k%L;
5+
while(counter++<L) {
6+
if(currentLoc>=L &&currentLoc%L==starti) {// this handles the case when currentLoc moves back to where started.
7+
currentLoc = ++starti;
8+
prevVal=nums[currentLoc];
9+
}
10+
11+
intnextLoc = (currentLoc+k)%L;// get index of next location
12+
intnextVal =nums[nextLoc];// get value at next location
13+
nums[nextLoc] =prevVal;// update value at next location
14+
prevVal =nextVal;// update previous value
15+
16+
currentLoc +=k;// move current to next location
17+
}
18+
}
19+
20+
publicstaticvoidmain(String[]args) {
21+
RotateArrayq =newRotateArray();
22+
23+
int[]nums = {1,2,3,4,5,6,7,8,9};
24+
intk =5;
25+
26+
q.rotate(nums,k);
27+
for(inti :nums) {
28+
System.out.print(i +" ");
29+
}
30+
System.out.println();
31+
}
32+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp