0189. 轮转数组 #22
utterances-bot
started this conversation in
Comments
0189. 轮转数组
#22
Replies: 19 comments · 3 replies
|
具体步骤3是否应该为[k,n-1]位置上的元素进行翻转 |
0 replies
嗯嗯。应该是 [k, n-1]。 感谢指正呀 |
0 replies
|
写的很好，mark，按照这个顺序刷题了 |
0 replies
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
start=0
end=len(nums)-1
length=end - start +1
direction = 1 #0 for going left, 1 for going right
k = k % length
while(k != 0):
# if k > length/2, rotate to opposite direction
if 2* k > length:
direction ^= 1
k = length - k
#swap k number between start and end
for i in range(k):
tmp=nums[start + i]
nums[start + i] = nums[end - k + 1 + i]
nums[end- k + 1 + i] = tmp
start += k * direction
end -= k * (direction^1)
length= end - start + 1
k = k % length自己想了个办法,时间复杂度也是O(n)但是慢一点,感觉我这个cycle数会更小一点来着,平均1n个cycle.可以参考看看为什么嘛 |
0 replies
|
我觉得这样的话 是很简便的 def Wheel_Array(array, k):
for x in range(k):
last = array[-1]
array.insert(0, last)
del array[-1]
return array |
0 replies
def rotate(nums, k):
L = [0 for i in range(len(nums))]
for i in range(len(nums)):
q = i + k
while q >= len(nums):
q = i + k - len(nums)
L[q] = nums[i]
return print（L）我在pycharm上能实现 但在leetcode上报错 有人帮我看看吗！ 感谢 |
0 replies
leetcode 上计算的是运行时间，只要复杂度一致，快一点慢一点不用太在意。 |
0 replies
这道题并不需要返回数组，而是需要直接在原数组上进行修改。 |
0 replies
|
可以用切片[::-1]代替翻转函数，会方便些 |
0 replies
|
为什么这样会改变外部的nums，我用 |
0 replies
|
请问为何需要 k = k % n 这一步？ |
1 reply
|
如果你要轮转的个数大于len(nums) 就会使得数组越界 |
for i in range(k):
nums.insert(0,nums[-1])
nums.pop(-1) |
0 replies
class Solution(object):
def rotate(self, nums, k):
for i in range(0,k):
tmp=nums[len(nums)-1];
for j in range(len(nums)-1,0,-1):
nums[j]=nums[j-1];
nums[0]=tmp;
return nums; |
0 replies
|
直接把最后的k个元素slice一下放到最前面，然后删掉最后的k个元素，这样时间是O(k) [插入耗时]，空间是O(1) class Solution:
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
n = len(nums)
k = k % n
if k == 0 or n <=1:
return
nums[:0] = nums[-k:]
del nums[-k:] |
2 replies
|
包括这样也是一样的逻辑，原地直接换 class Solution:
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
n = len(nums)
k = k % n
nums[:] = nums[-k:] + nums[:-k] |
|
我还好奇这是什么语言，ai 了一下这是python ,可以直接插k 个到前面，其实还是至少得申请o(k) 个内存空间，所以你这个不是O（1）。 |
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
if k == 0: # no need to move
return
k = k % len(nums)
index = len(nums) - k
nums[:] = nums[index:] + nums[:index] |
0 replies
|
0 replies
void rotate(int* nums, int numsSize, int k) { // 空间复杂度o(n). 如果要o(1),估计就是申请一个中间变量去搞
if(k>=numsSize){
k=k%numsSize; // 一个numsSize 就恢复到原样。
}
int* copy = malloc(numsSize*sizeof(int));// 申请一个一样大小的数组
memset(copy,0,numsSize); //清0 ，不然有脏东西。
memmove(copy,(nums+numsSize-k),k*sizeof(int)); // 尾巴复制到前面
memmove(©[k],&nums[0],(numsSize-k)*sizeof(int)); // nums头复制到copy后面
memmove(&nums[0],©[0],numsSize*sizeof(int)); // copy 复制给 nums
} |
0 replies
class Solution:
def wheelTrans(self,nums,k):
L=len(nums)
newNums=[0]*L
for i in range(L):
newNums[i]=nums[(i-k+L)%L]
return newNums |
0 replies
|
额外结构 class Solution {
public void rotate(int[] nums, int k) {
int[] temp = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
temp[(i + k) % nums.length] = nums[i];
}
System.arraycopy(temp, 0, nums, 0, temp.length);
}
}数组反转 class Solution {
public void rotate(int[] nums, int k) {
if (nums == null || nums.length < 2)return;
k = k % nums.length;
reverseArray(nums, 0, nums.length - 1);
reverseArray(nums, 0, k - 1);
reverseArray(nums, k, nums.length - 1);
}
public void reverseArray(int[] nums, int start, int end) {
for (int i = start, x = end; i < x; i++, x--) {
int temp = nums[i];
nums[i] = nums[x];
nums[x] = temp;
}
}
} |
0 replies
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Uh oh!
There was an error while loading. Please reload this page.
Uh oh!
There was an error while loading. Please reload this page.
0189. 轮转数组 | 算法通关手册
要求：将数组中的元素向右移动 k 个位置。
说明：
https://algo.itcharge.cn/Solutions/0100-0199/rotate-array
All reactions