Rotate Array

Rotate Array

问题：

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].

思路：

　　插入排序

　　翻转数组

我的代码：

public class Solution {
    public void rotate(int[] nums, int k) {
        if(nums == null || nums.length == 0)    return;
        int n = nums.length;
        k = k % n;
        if(k == n || k == 0)    return;
        for(int i = n - k; i < n; i++)
        {
            int tmp = nums[i];
            for(int j = i; j > 0; j--)
            {
                nums[j] = nums[j-1];
            }
            nums[0] = tmp;
        }
        return;
    }
}

他人代码：

public class Solution {
    public void rotate(int[] nums, int k) {
        if(nums == null || nums.length == 0)    return;
        int n = nums.length;
        k = k % n;
        reverse(nums, 0, n-k-1);
        reverse(nums, n-k, n-1);
        reverse(nums, 0, n-1);
        return;
    }
    public void reverse(int[] nums, int left, int right)
    {
        while(left < right)
        {
            int tmp = nums[left];
            nums[left] = nums[right];
            nums[right] = tmp;
            left ++;
            right --;
        }
    }
}

学习之处：

• 一个好的思路是至关重要的，本以为插入排序就可以解决这个问题了O(n²)，但是通过这种直接的翻转数组，翻转数组，再翻转数组立马解决了这个问题，长知识了。时间复杂度O(n)
• 正的不行倒着来，倒着来包括指针在后面，还包括对数组进行翻转