双指针.md

双指针

1.数组中数字的轮转(LeetCode 第189题)

//用额外数组来存放移动后的数组，然后再用assign函数复制回元素组
class Solution {
public:
    void rotate(vector<int>& nums, int k) 
    {
        int n = nums.size();
        vector<int> temp(n);

        for(int i = 0 ; i < n ; i ++)
            temp[(i + k) % n] = nums[i];
        
        nums.assign(temp.begin() , temp.end());
    }
};

时间复杂度O(n) ， 空间复杂度O(n)

//数组翻转
class Solution {
public:
    void reverse(vector<int>& nums, int start, int end) {
        while (start < end) {
            swap(nums[start], nums[end]);
            start += 1;
            end -= 1;
        }
    }

    void rotate(vector<int>& nums, int k) {
        k %= nums.size();
        reverse(nums, 0, nums.size() - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.size() - 1);
    }
};

先将整个数组翻转，然后以移动次数k为边界，分别翻转两边的元素

时间复杂度O(n) ， 空间复杂度O(1)