leetcode——轮转数组(java)
给定一个整数数组 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]
解题方法:(双指针+排序)
1.经分析得出我们可以使用双指针与排序来进行解题,首先我们先写一个辅助函数来交换双指针指向的元素。
2.首先我们需要将数组逆序排序,然后我们再将前k
个元素逆序排序,然后将剩下的元素逆序排序。
class Solution {
public void rotate(int[] nums, int k) {
int n = nums.length;
k %= n;
reverse(nums, 0, n - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, n - 1);
}
private void reverse(int[] nums, int i, int j) {
while(i < j) {
int temp = nums[i];
nums[i++] = nums[j];
nums[j--] = temp;
}
}
}