LeetCode 189.配列の回転(Java)



Leetcode 189 Rotate Array



トピック:

配列が与えられたら、配列を右にkステップ回転します。ここで、kは負ではありません。

例1:
入力:[1,2,3,4,5,6,7]およびk = 3
出力:[5,6,7,1,2,3,4]
説明:
右に1ステップ回転します:[7,1,2,3,4,5,6]
右に2ステップ回転します:[6,7,1,2,3,4,5]
右に3ステップ回転します:[5,6,7,1,2,3,4]



例2:
入力:[-1、-100、3、99]およびk = 2
出力:[3,99、-1、-100]
説明:
右に1ステップ回転します:[99、-1、-100,3]
右に2ステップ回転します:[3,99、-1、-100]

解決:

n = 7、k = 3と仮定します
元の配列:[1,2,3,4,5,6,7]
すべての数値を反転した後:[7,6,5,4,3,2,1]
最初のk桁を逆にした後:[5,6,7,4,3,2,1]
n-k桁を反転した後:[5,6,7,1,2,3,4]



//When we rotate the array k times, k\%n tail elements will be moved to the head, and the remaining elements will be moved backward //Invert all elements first, then invert the first k elements, and then invert n-k elements in the back, you can get the desired result class Solution { public void rotate(int[] nums, int k) { k%=nums.length reverse(nums,0,nums.length-1) reverse(nums,0,k-1) reverse(nums,k,nums.length-1) } public void reverse(int[] nums,int start,int end){ while(start<end){ int temp=nums[start] nums[start]=nums[end] nums[end]=temp start++ end-- } } }

当局は、方法1:暴力の解決策など、さまざまな方法を提供します

//The easiest way is to rotate k times, rotating the array by 1 element each time //Time complexity: O(n*k), each element is moved 1 step O(n), k times O(k) //Space complexity: O(1), no extra space is used public class Solution { public void rotate(int[] nums, int k) { int temp, previous for (int i = 0 i < k i++) { previous = nums[nums.length - 1] for (int j = 0 j < nums.length j++) { temp = nums[j] nums[j] = previous previous = temp } } } }

方法2:追加のアレイを使用する

//Use an extra array to put each element in the correct position, which is the subscript i in the original array, put it in the position of (i+k)\% array length, and then put the new Copy the array into the original array //Time complexity: O(n), the number needs to be traversed into the new array, and the other side will copy the elements of the new array back to the original array //Space complexity: O(n), another array needs space of the original array length public class Solution { public void rotate(int[] nums, int k) { int[] a = new int[nums.length] for (int i = 0 i < nums.length i++) { a[(i + k) % nums.length] = nums[i] } for (int i = 0 i < nums.length i++) { nums[i] = a[i] } } }

方法3:リング交換を使用する
各数値を直接最終位置に配置すると、元の要素が失われます。したがって、置き換えられた数値を変数tempに保存する必要があります。次に、置き換えられた数値(temp)を正しい位置に配置し、このプロセスをn回続行します。ここで、nは配列の長さです。これは、配列内のすべての要素を移動する必要があるためです。ただし、n%k = = 0の場合、k = k%nの場合、この方法には問題がある可能性があります(kがnより大きい場合、k回移動することは実際にはk%n回移動することと同じであるため)。この場合、すべての番号をトラバースせずに開始番号に戻ることがわかります。この時点で、次の番号から同じプロセスを繰り返す必要があります。
それでは、上記の方法の証明を見てみましょう。配列にn個の要素があり、kが必要な移動の数であるとします。さらに、n%k = 0と仮定します。最初のラウンドでは、すべての携帯電話番号の添え字iがi%k == 0を満たします。これは、kステップジャンプするたびに、k桁離れた添え字の数にしか到達しないためです。各ラウンドで、n / k個の要素を移動します。次のラウンドでは、i%k == 1を満たす位置の数を移動します。このラウンドは、i%k == 0に再び会うまで、この時点でi = kまで続きます。このとき、正しい位置にk *(n / k)= n個の数字があります。したがって、すべての数字は正しい位置にあります。
例:nums:[1、2、3、4、5、6]
k:2
[、、(img-ln5LrHnS-1580141974270)(evernotecid:// D179F99A-2586-4880-B233-60EB587FAA44 / appyinxiangcom / 21144302 / ENResource / p102)]



//Time complexity: O(n), only traversed each element once //Space complexity: O(1), using a constant amount of extra space public class Solution { public void rotate(int[] nums, int k) { k = k % nums.length int count = 0 for (int start = 0 count < nums.length start++) { int current = start int prev = nums[start] do { int next = (current + k) % nums.length int temp = nums[next] nums[next] = prev prev = temp current = next count++ } while (start != current) } } }