力扣189.かいてんはいれつ

力扣189.かいてんはいれつ

解法一

解法二

解法三

3つの解法、解法1は簡単に考えられますが、後の2つの解法は比較的巧みで、ここで記録しておきます.
解法一
配列を1つずつ後ろに移動するたびにk%numsを移動する.length回(k%nums.lengthはnums.lengthをずらす倍数回がずらさないに相当するため)

//     ：O(kn)
//     ：O(1)
class Solution {
    public void rotate(int[] nums, int k) {
        if (nums.length == 0)
			return;
		int last = nums[nums.length - 1];
		for (int i = 0; i < k % nums.length; i++) {
			for (int j = nums.length - 1; j > 0; j--) {
				nums[j] = nums[j - 1];
			}
			nums[0] = last;
			last = nums[nums.length - 1];
		}
    }
}

解法二
①kビットは1単位で移動し、毎回後kビットを前kビットと交換し、前kビットが正しい位置に到達するようにする.②このとき、残りの位置は、kビットを移動する必要がある新しい配列を形成し、1を繰り返し、1の再帰に類似する.

//     ：O(n)
//     ：O(1)
class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k %= n;
        //         ，  k        ，  n-k        k        ，    
        for (int start = 0; start < nums.length && k != 0; n -= k, start += k, k %= n) {
            for (int i = 0; i < k; i++) {
                int temp = nums[start + i];
                nums[start + i] = nums[nums.length - k + i];
                nums[nums.length - k + i] = temp;
            }
        }
    }
}

解法三
この解法は最も巧みで、私には考えられないと思いますが...これも回転配列というタイトルに最も合っています.①配列全体を反転させる(理解:後方シフトkビットは、実は元の配列の後方kビットを一番前に移動したが、前後の順序は変わらない.直接反転した後、後方kビットを一番前に移動したが、順序が逆である.)②前k位を反転③後n-k位を反転

//     ：O(n)
//     ：O(1)
public void rotate(int[] nums, int k) {
        int n = nums.length;
        k %= n;
        reverse(nums, 0, n - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, n - 1);
    }


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