傳送門:旋轉陣列
又是面向評論區編程的一天,打開評論,選中熱門,Ctrl+C,V,看著上面時間超過100%,我覺得自己又行了!!!
最先想到的就是線性移動,回圈k次,每次取出陣列中最后一個數,然后所有數字后移一個位置
但是這種方法太慢了,那么有沒有更簡單一點的方法呢!
顯然是有的!
這個時候打開評論區,選中我們需要的代碼
提交,又是水題的一天!!!
我們想到,當移動k次后,尾部的k mod n個元素就會被移動到陣列的頭部,其余元素往后移動k mod n個位置
該方法為陣列的翻轉：我們可以先將所有元素翻轉，這樣尾部的 k mod n 個元素就被移至陣列頭部，然后我們再翻轉[0,k mod n -1]區間的元素和 [k mod n,n-1]區間的元素即能得到最后的答案，
Code:
class Solution {
public void rotate(int[] nums, int k) {
for (int i = 0; i < k; i++) {
int temp = nums[nums.length - 1];
for (int i1 = nums.length - 1; i1 >= 1; i1--) {
nums[i1] = nums[i1-1];
}
nums[0] = temp;
}
}
}
Code:
class Solution {
public void rotate(int[] nums, int k) {
int n=nums.length;
k=k%n;
reverse(nums,0,n-1);
reverse(nums,k,n-1);
reverse(nums,0,k-1);
}
private static void reverse(int[] nums,int start,int end){
while(start<end){
int temp=nums[start];
nums[start]=nums[end];
nums[end]=temp;
start++;
end--;
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/246824.html
標籤：java
上一篇：Java集合4-3