力扣之轮转数组

题目:你一个数组,将数组中的元素向右轮转 k 个位置,其中 k 是非负数

例:输入: nums = [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]

要点:一般来说我是直接对于数组复制与另一个数组然后for循环替换位置,但这样做有些麻烦而且会很容易发生错误,然后还有另一个方法,就是我们可以使用额外的数组来将每个元素放至正确的位置。用 nn 表示数组的长度,我们遍历原数组,将原数组下标为 ii 的元素放至新数组下标为 (i+k)\bmod n(i+k)modn 的位置,最后将新数组拷贝至原数组即可。用取模的方式来计算是哪个位置。其中还有的问题就是,是去一个新值进行循环替代,还是找一个新数组进行复制以防移动的数覆盖原先的数,当然新数组肯定是方便一些。

结果:(暴力)class Solution {

public:

    void rotate(vector<int>& nums, int k) {

        int n = nums.size();

        vector<int> newArr(n);

        for (int i = 0; i < n; ++i) {

            newArr[(i + k) % n] = nums[i];

        }

        nums.assign(newArr.begin(), newArr.end());

    }

};

有一种更巧妙的的是反转:将所有元素反转。然后反转前 k 个元素,再反转后面 n-kn−k 个元素,就能得到想要的结果。

原始数组 : 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 --> 结果

代码:var rotate = function(nums, k) {

    k=k%nums.length;

    reverse(nums,0,nums.length-1);

    reverse(nums,0,k-1);

    reverse(nums,k,nums.length-1);

};

function reverse(arr,start,end){

    while(start<end){

        var temp=arr[start];

        arr[start]=arr[end];

        arr[end]=temp;

        start++;

        end--;

    }

}

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容