网站备案组织机构代码,网站后台加什么后缀,鞍山做网站优化公司,大型门户网站开发leetcode 189 轮转数组
题目 给定一个整数数组 nums#xff0c;将数组中的元素向右轮转 k 个位置#xff0c;其中 k 是非负数。 示例 1: 输入: 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] 向…leetcode 189 轮转数组
题目 给定一个整数数组 nums将数组中的元素向右轮转 k 个位置其中 k 是非负数。 示例 1: 输入: 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] 示例 2: 输入nums [-1,-100,3,99], k 2 输出[3,99,-1,-100] 解释: 向右轮转 1 步: [99,-1,-100,3] 向右轮转 2 步: [3,99,-1,-100] https://leetcode.cn/problems/rotate-array/description/
解法一
思路创建新数组依次拷贝原数组的元素到新数组注意下标的转换 时间复杂度遍历两次O(n) 空间复杂度使用了新数组resO(n)
class Solution {public void rotate(int[] nums, int k) {// 方法1新数组保存到新数组的正确位置// i - (ik)%nint n nums.length;int[] res new int[n];for (int i 0; i n; i) {res[(ik)%n] nums[i];}for (int j 0; j n; j) {nums[j] res[j];}}
}解法二
思路三次翻转 时间复杂度三次翻转一共2N次时间复杂度O(n) 空间复杂度没有使用额外数组O(1)
class Solution {public void rotate(int[] nums, int k) {// 方法二假设数组长度为n按照下面步骤紧张翻转// 全部数组轮转 [0, n-1][1234567]-[7654321]// 前半部分翻转[0, k-1], [7654321]-[5674321]// 后半部分翻转[k, n-1], [5674321]-[5671234]int n nums.length;k k % n;reverse(nums, 0, n-1);reverse(nums, 0, k-1);reverse(nums, k, n-1);}void reverse(int[] nums, int start, int end) {while (start end) {int temp nums[start];nums[start] nums[end];nums[end] temp;start;end--;}}}
