室内设计联盟官方网站登录,安阳网站建设策划,谷歌网站英文,电子商务网站建设考题原题请见#xff1a;Leetcode189-旋转数组
1、题目描述 2、题目分析
首先容易想到的最简单的方案#xff0c;是算出来移动K步之后#xff0c;新数组的每一个坐标与原坐标的映射关系#xff0c;然后根据映射关系放到一个全新的数组#xff0c;再把新数组的值赋给原数组。…原题请见Leetcode189-旋转数组
1、题目描述 2、题目分析
首先容易想到的最简单的方案是算出来移动K步之后新数组的每一个坐标与原坐标的映射关系然后根据映射关系放到一个全新的数组再把新数组的值赋给原数组。
但题目描述的进阶方案我们应该考虑使用 O(1) 复杂度实现。 这里不啰嗦直接说结论 任何有关数组的旋转、对称、平移的题目优先去把题目转换成几次基本的对称。 大多数情况下都能通过有限次的对称解决。 例如本题 假设输入条件是[1,2,3,4,5,6,7] k 3 第一步先整体左右对称[7,6,5,4,3,2,1] 第二步根据 k 3做一个分割线 [7,6,5 | 4,3,2,1] 第三步分割线左边的内容做对称分割线右边的内容做对称 [5,6,7 | 1,2,3,4]
3、题解
class Solution {public void rotate(int[] nums, int k) {// 考虑使用原地对称的算法解决这个问题// 例如[1,2,3,4,5,6,7] k 3// 第一步先整体左右对称[7,6,5,4,3,2,1]// 第二步根据 k 3做一个分割线 [7,6,5 | 4,3,2,1]// 第三步分割线左边的内容做对称分割线右边的内容做对称 [5,6,7 | 1,2,3,4]int minK k % nums.length;symmetrized(nums, 0, nums.length - 1);symmetrized(nums, 0 , minK - 1);symmetrized(nums, minK, nums.length - 1);}private void symmetrized(int[] nums, int start, int end) {int mid (start end 1) / 2;for (int i 0; i start mid; i) {int temp nums[start i];nums[start i] nums[end - i];nums[end - i] temp;}}
}
