leetcode/code/lc189.java at master · mJackie/leetcode · GitHub

History

51 lines (50 loc) · 1.6 KB

Raw

package code;

* 189. Rotate Array

* 题意：数组向后移几位，超出末尾的补到前边

* 难度：Easy

* 分类：Array

* 思路：一种环状替换，别忘了可能是多个环。

* reverse 的方法，先整体反转，再按照k划分成两个数组分别反转

* Tips：

public class lc189 {

public void rotate(int[] nums, int k) {

if(nums.length<2) return;

int sum = 0;

for (int start_index = 0; start_index < nums.length ; start_index++) { //可能多个环，用sum判断是否停止

if(sum==nums.length) break;

int curr_index = start_index;

int next_index = (start_index+k)%nums.length;

int temp1 = nums[start_index];

int temp2 =0;

while(next_index!=start_index){

sum++;

temp2 = nums[next_index];

nums[next_index] = temp1;

temp1 =temp2;

curr_index = next_index;

next_index = (curr_index+k)%nums.length;

}

nums[start_index] = temp1;

sum++;

}

public void rotate2(int[] nums, int k) {

if(nums.length<2) return;

k = k%nums.length; //处理k>length的case

reverse(nums, 0, nums.length-1);

reverse(nums, 0, k-1);

reverse(nums, k, nums.length-1);

}

public void reverse(int[] nums, int begin, int end){

while(begin<end){

int temp = nums[begin];

nums[begin] = nums[end];

nums[end] = temp;

begin++;

end--;

}

return;

}

leetcode/code/lc189.java at master · mJackie/leetcode · GitHub

Expand file tree

Breadcrumbs

lc189.java

Latest commit

History

Breadcrumbs

lc189.java

File metadata and controls