最新消息:XAMPP默认安装之后是很不安全的,我们只需要点击左方菜单的 "安全"选项,按照向导操作即可完成安全设置。

数组篇3_旋转数组解法思路

XAMPP相关 admin 420浏览 0评论

来源:LeetCode

难度:中等

描述:

给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。

进阶:

尽可能想出更多的解决方案,至少有三种不同的方法可以解决这个问题。

你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗?

drf0032

分析:题意是要将一维数组中的元素进行移位,其中k代表每个元素移动的步数,当k等于数组大小时,相当于没有移动,大于数组大小相当于重新开始移动一步,即咱们可以只考虑移动步数小于n,我们可以把数组分为两截,一截是后面k个元素,一截是前面n-k个元素,最终的目的就是将后面k个按顺序放到前面去,我们可以采用顺序遍历、辅助空间、翻转等方法来解题,如下

题外话:采用额外空间的方式解题简直不要太爽

 

解题

方法一:顺序移动法

思路:将数组中每个元素按照题意的方式移动k(k=k%n)步,注意最后一个元素的保存以及对第一个元素的替换

代码:

 1public void rotate(int[] nums, int k) {
 2    int n = nums.length;
 3    k = k % n;
 4    for(int i = 0; i < k; i ++){
 5        //先保留最后一个元素
 6        int temp = nums[n - 1];
 7        //不断用前一个覆盖后一个
 8        for(int j = n - 2; j >= 0; j --){
 9            nums[j + 1] = nums[j];
10        }
11        //将第一个元素替换为最后一个
12        nums[0] = temp;
13    }
14}

时间复杂度:O(n2)

空间复杂度:O(1) 

方法二:辅助空间法

思路:辅助空间也可分为两种方法,一种是申请和原数组一样大小的辅助数组,然后将从k(k=k%n)到n之间的数据先放入辅助数组,然后将0到k之间的数据再放入辅助数组,只有整体替换即可,还有一种是申请k个元素的辅助数组,然后将n-k 到n之间的数据放入辅助数组,0到n-k之间的数据整体向后移k步,最后将辅助空间的数据放入数组头部即可,这里将第二种方式实现下

代码:

 1public void rotate(int[] nums, int k) {
 2    int length = nums.length;
 3    int copyLen = k % length;
 4    if (copyLen == 0) {
 5        return;
 6    }
 7    //将后半截k个元素复制下来
 8    int[] copy = Arrays.copyOf(nums, copyLen);
 9    for (int i = length - 1; i >= 0; i--) {
10        // 0到copyLen 之间的元素向后移k步
11        // i+k 的位置保存的是原来的i的数值
12        nums[(i + copyLen) % length] = nums[i];
13    }
14    //这时候,0-copyLen位置的数据,向后移动了k一部分位置。
15    for (int i = 0; i < copyLen; i++) {
16        nums[(i + copyLen) % length] = copy[i];
17    }
18}

时间复杂度:O(n)

空间复杂度:O(k) 

方法三:翻转法

思路:先反转全部数组,在反转前k个,最后在反转剩余的,如下图

drf00032

代码:

 1public void rotate(int[] nums, int k) {
 2    int length = nums.length;
 3    k %= length;
 4    //先反转全部的元素
 5    reverse(nums, 0, length - 1);
 6    //在反转前k个元素
 7    reverse(nums, 0, k - 1);
 8    //接着反转剩余的
 9    reverse(nums, k, length - 1);
10}
11
12//把数组中从[start,end]之间的元素两两交换,也就是反转
13public void reverse(int[] nums, int start, int end) {
14    while (start < end) {
15        int temp = nums[start];
16        nums[start++] = nums[end];
17        nums[end--] = temp;
18    }
19}

时间复杂度:O(n)

空间复杂度:O(1) 

方法四:原地循环替换法

思路:咱们将第一个元素移到第k(k=k%n)位上,将第k位的移动到第(k+k)%n上…,依次类推,当咱们将每个元素都替换一遍后,即完成整个数组的旋转,其中标记数组可以用计数的方式替代,此处用数组标记更清晰易懂

代码:

 1public static void rotate(int[] nums, int k) {
 2    //保存将要被覆盖的元素
 3    int pre = nums[0];
 4    int index = 0;
 5    int length = nums.length;
 6    //利用数组标记该元素是否移动过
 7    boolean[] visited = new boolean[length];
 8    for (int i = 0; i < length; i++) {
 9        index = (index + k) % length;
10        if (visited[index]) {
11            //如果访问过,我们直接从他的下一个元素开始 
12            index = (index + 1) % length;
13            pre = nums[index];
14            i--;
15        } else {
16            //修改标记
17            visited[index] = true;
18            //元素交换
19            int temp = nums[index];
20            nums[index] = pre;
21            pre = temp;
22        }
23    }
24}

时间复杂度:O(n)

空间复杂度:O(n) n为标记数组

 

以上仅是个人思路解法

转载请注明:XAMPP中文组官网 » 数组篇3_旋转数组解法思路

您必须 登录 才能发表评论!