刷题|2021-07-16 力扣 189题数组翻转(三种方法) 算法|leetcode

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

尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
你可以使用空间复杂度为 O(1) 的原地算法解决这个问题吗？

例子: 【刷题|2021-07-16 力扣 189题数组翻转(三种方法)】

文章图片

方法一：暴力求解

int n = nums.length; k %= n; //当k>n时从头计算 for (int i = 0; i < k; i++) { //控制数组移动次数 int temp = nums[n - 1]; //记录末尾值 for (int j = n - 1; j > 0; j--) { //数组向后移动一次 nums[j] = nums[j - 1]; } nums[0] = temp; //交换头尾 } } //时间复杂度O(kn) //空间复杂度O(1)

方法二:旋转数组

void reverse(vector& nums, int start , int end){ int temp; while(start < end) { temp = nums[start]; nums[start++] = nums[end]; nums[end--] = temp; } } //翻转数组的函数 void rotate(vector& nums, int k) { int n = nums.size(); k % = n; //同上 reverse(nums , 0 , n - 1); //全体反转 reverse(nums , 0 , k - 1); //前半部分转回 reverse(nums , k , n - 1); //后半部分转回 } //时间复杂度O(2n) //空间复杂度O(1)

方法三:增加数组