leetcode189-- Rotate Array

leetcode189-- Rotate Array

给定一个数组,rotate这个数组,即往前走k步,求得到的数组

其实只需要走k%L步就可以了,其中L是数组的长度。

所以就相当于是将后面的k个弄到前面来,所以可以分成三步

第一步,把后面的k个反过来 第二步,把前面的L-k个反过来 第三步,把整体再反过来

class Solution(object):
    def rotate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        if k is None or k <=0:
            return
        k, end = k%len(nums), len(nums)-1
        # 翻转前面的,
        self.reverse(nums, 0, end-k)
        # 翻转后面的
        self.reverse(nums, end-k+1, end)
        # 整体再翻转一次
        self.reverse(nums, 0, end)
        
    def reverse(self, nums, start, end):
        while start<end:
            nums[start], nums[end] = nums[end], nums[start]
            start, end = start+1, end -1
            
    

之前也用c++写过一次, 之前我是一个一个地算的

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int now=0, next;
        int temp1, temp2=nums[0];
        for(int j=0,i=0;j<nums.size();j++){
            temp1 = temp2;
            now = (k+now)%nums.size();
            temp2 = nums[now];
            nums[now]= temp1;
            
            if(now==i){
                now = ++i;
                temp2 = nums[now];
            }
        }
        
    }
};

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦