首页 > itarticle > 189Rotate_Array给定一

189Rotate_Array给定一

admin 11月 13, 2020 0

189Rotate_Array

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

暴力：往右移动k次

int n = nums.size(); 
k = k % n;
while (k--) {
    int tmp = nums[n - 1];
    for (int i = n - 1; i > 0; ++i) {
        nums[i] = nums[i - 1];
    }
    nums[0] = tmp;
}

//[1, 2, 3, 4, 5, 6, 7], k = 3

reverse(nums.begin(), nums.end());

//[7, 6, 5, 4, 3, 2, 1]

auto it1 = nums.begin();
auto it2 = nums.begin();
while (k--) {
	it1++;
    it2++;
}
reverse(nums.begin(), it1);

//[5, 6, 7, 4, 3, 2, 1]

reverse(it2, nums.end()); //iterator 最好只用一次，vector被改变之后，iterator可能指向意料之外的地方

//[5, 6, 7, 1, 2, 3, 4]

reverse的实现

void (int *l, int *r) {
    --r;
    for (; l < r; ++l, --r) {
        int tmp = *l;
        *l = *r;
        *r = tmp;
    }
}

void rotate(int* nums, int numsSize, int k) {
    k %= numsSize;
    reverse(nums, nums + numsSize);
    reverse(nums, nums + k);
    reverse(nums + k, nums + numsSize);
}