LeetCode_双指针_中等_189. 轮转数组
2023-09-27 14:25:46 时间
1.题目
给你一个数组,将数组中的元素向右轮转 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]
提示:
1 <= nums.length <= 105
-231 <= nums[i] <= 231 - 1
0 <= k <= 105
进阶:
尽可能想出更多的解决方案,至少有三种不同的方法可以解决这个问题。
你可以使用空间复杂度为 O(1) 的原地算法解决这个问题吗?
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/rotate-array
2.思路
(1)辅助数组
(2)环状替换
(3)数组翻转
3.代码实现(Java)
//思路1————辅助数组
class Solution {
public void rotate(int[] nums, int k) {
int length = nums.length;
k %= length;
//创建辅助数组,用于存放轮转之前的元素值
int[] tmp = Arrays.copyOf(nums, length);
//进行数组轮转
for (int i = 0; i < length; i++) {
nums[(i + k) % length] = tmp[i];
}
}
}
//思路2————环状替换
class Solution {
public void rotate(int[] nums, int k) {
int n = nums.length;
k = k % n;
int count = gcd(k, n);
for (int start = 0; start < count; ++start) {
int current = start;
int prev = nums[start];
do {
int next = (current + k) % n;
int temp = nums[next];
nums[next] = prev;
prev = temp;
current = next;
} while (start != current);
}
}
public int gcd(int x, int y) {
return y > 0 ? gcd(y, x % y) : x;
}
}
//思路3————数组翻转
class Solution {
public void rotate(int[] nums, int k) {
k %= nums.length;
reverse(nums, 0, nums.length - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, nums.length - 1);
}
public void reverse(int[] nums, int start, int end) {
while (start < end) {
int temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start += 1;
end -= 1;
}
}
}
相关文章
- LeetCode每日一练 —— 26. 删除有序数组中的重复项
- 【LeetCode】轮转数组 [M](数组)
- 【LeetCode】跳跃游戏 [M](模拟)
- 【LeetCode】阶乘后的零 [M](数学)
- 最小 XOR leetcode第 313 场周赛 第三题
- <LeetCode> 题31:数组划分
- LeetCode_前缀和_哈希表_困难_2488.统计中位数为 K 的子数组
- LeetCode_二分搜索_困难_154.寻找旋转排序数组中的最小值 II
- LeetCode_贪心算法_中等_1775.通过最少操作次数使数组的和相等
- LeetCode_逆向思维_中等_453.最小操作次数使数组元素相等
- LeetCode_区间问题_中等_1834. 单线程 CPU
- LeetCode_排序_简单_350.两个数组的交集II
- LeetCode·每日一题·1630. 等差子数组·模拟
- LeetCode·每日一题·795.区间子数组个数·脑筋急转弯
- LeetCode·每日一题·1636.按照频率将数组升序排序·哈希
- LeetCode·每日一题·1464.数组中两元素的最大乘积·枚举
- LeetCode·581.最短无序连续子数组·双指针
- LeetCode·26.删除有序数组中的重复项·双指针
- Leetcode[110]-Balanced Binary Tree
- leetCode解题报告5道题(九)
- [LeetCode] 290. Word Pattern 单词模式
- [LeetCode] 152. Maximum Product Subarray 求最大子数组乘积
- [LeetCode] 227. Basic Calculator II 基本计算器 II
- [LeetCode] 7. Reverse Integer 翻转整数
- leetcode算法:Island Perimeter
- LeetCode 1385.两数组间的距离值