LeetCode每日一題: 旋轉(zhuǎn)數(shù)組（No.189）

FreeZinG 發(fā)布于2019-05-22 19:46 / 906人閱讀

摘要：題目旋轉(zhuǎn)數(shù)組給定一個(gè)數(shù)組，將數(shù)組中的元素向右移動(dòng)個(gè)位置，其中是非負(fù)數(shù)。例如將到反轉(zhuǎn)將到反轉(zhuǎn)全部翻轉(zhuǎn)得到最后結(jié)果。這里要注意下還有這樣的情況即大于數(shù)組長(zhǎng)度的情況。次旋轉(zhuǎn)次旋轉(zhuǎn)轉(zhuǎn)回來(lái)了次旋轉(zhuǎn)次旋轉(zhuǎn)轉(zhuǎn)回來(lái)了次旋轉(zhuǎn)所以這里的有效等于對(duì)數(shù)組長(zhǎng)度求余。

題目：旋轉(zhuǎn)數(shù)組

給定一個(gè)數(shù)組，將數(shù)組中的元素向右移動(dòng) k 個(gè)位置，其中 k 是非負(fù)數(shù)。

示例：

輸入: [1,2,3,4,5,6,7] 和 k = 3
輸出: [5,6,7,1,2,3,4]
解釋:
向右旋轉(zhuǎn) 1 步: [7,1,2,3,4,5,6]
向右旋轉(zhuǎn) 2 步: [6,7,1,2,3,4,5]
向右旋轉(zhuǎn) 3 步: [5,6,7,1,2,3,4]

輸入: [-1,-100,3,99] 和 k = 2
輸出: [3,99,-1,-100]
解釋: 
向右旋轉(zhuǎn) 1 步: [99,-1,-100,3]
向右旋轉(zhuǎn) 2 步: [3,99,-1,-100]

思考：

這道題有一種巧妙地利用反轉(zhuǎn)的做法。
首先將第0個(gè)到第k個(gè)元素反轉(zhuǎn)，再將第k+1到末尾元素反轉(zhuǎn)，最后再將全部元素反轉(zhuǎn)即可。
例如：[1,2,3,4,5,6,7]   k = 3
將0到3反轉(zhuǎn)：[4,3,2,1,5,6,7]
將4到6反轉(zhuǎn)：[4,3,2,1,7,6,5]
全部翻轉(zhuǎn)：[5,6,7,1,2,3,4] 得到最后結(jié)果。

這里要注意下還有這樣的情況：[1,2]    k = 5    即k大于數(shù)組長(zhǎng)度的情況。
這里可以發(fā)現(xiàn)數(shù)組旋轉(zhuǎn)次數(shù)等于數(shù)組長(zhǎng)度時(shí)，旋轉(zhuǎn)后的數(shù)組與初始數(shù)組相同，轉(zhuǎn)了一圈又回來(lái)了。
1次旋轉(zhuǎn)：[2,1]
2次旋轉(zhuǎn): [1,2]    轉(zhuǎn)回來(lái)了
3次旋轉(zhuǎn)：[2,1]
4次旋轉(zhuǎn): [1,2]    轉(zhuǎn)回來(lái)了
5次旋轉(zhuǎn)：[2,1]
所以這里的有效k等于k對(duì)數(shù)組長(zhǎng)度求余。

實(shí)現(xiàn)：

    class Solution {
    public void rotate(int[] nums, int k) {
        int length = nums.length;
        k %= length;
        reverse(nums, 0, length - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, length - 1);
    }

    private void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start++] = nums[end];
            nums[end--] = temp;
        }
    }
}