• 软件:1160
  • 资讯:41601|
  • 收录网站:97880|

IT精英团

504,旋转数组的3种解决方式

504,旋转数组的3种解决方式

浏览次数:
评论次数:
编辑: 景同
信息来源: 51CTO博客
更新日期: 2021-06-13 00:18:39
摘要

504,旋转数组的3种解决方式, Therearemanythingsthatseemimpossibleonlysolongasonedoesnotattemptthem. 很多事情看起来不可能只是因为没有人尝试过。问题描述给定一个数组,将数组中的元素向右移动k个位置,其中k是非负数。 示例1:输入:nums=[1,2,3,4,5,6,7],k=3输出:[5,6,

  • 资讯详情

There are many things that seem impossible only so long as one does not attempt them. 

很多事情看起来不可能只是因为没有人尝试过。

问题描述

给定一个数组,将数组中的元素向右移动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<=2*10^4

  • -2^31<=nums[i]<=2^31-1

  • 0<=k<=10^5

使用临时数组解决

这题是让把数组中的每个元素都往右移动k位。最简单的一种解决方式就是使用一个临时数组解决,先把原数组的值存放到一个临时数组中,然后再把临时数组的值重新赋给原数组,重新赋值的时候要保证每个元素都要往后移k位,如果超过数组的长度就从头开始,所以这里可以使用(i + k) % length来计算重新赋值的元素下标

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

 1public void rotate(int nums[], int k) {
2    int length = nums.length;
3    int temp[] = new int[length];
4    // 把原数组值放到一个临时数组中,
5    for (int i = 0; i < length; i++) {
6        temp[i] = nums[i];
7    }
8    // 然后在把临时数组的值重新放到原数组,
9    // 并且往右移动k位
10    for (int i = 0; i < length; i++) {
11        nums[(i + k) % length] = temp[i];
12    }
13}

部分元素多次反转

还有一种方式就是先反转全部数组,在反转前k个,最后在反转剩余的,如下所示

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

 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}

其实还可以在调整下,先反转前面的,接着反转后面的k个,最后在反转全部,原理都一样

 1public void rotate(int[] nums, int k) {
2    int length = nums.length;
3    k %= length;
4    //先反转前面的
5    reverse(nums, 0, length - k - 1);
6    //接着反转后面k个
7    reverse(nums, length - k, length - 1);
8    //最后在反转全部的元素
9    reverse(nums, 0, 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}

环形旋转

类似约瑟夫环一样,把数组看作是环形的,每一个都往后移动k位,这个很好理解,画个图来看一下

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

但这里有一个坑,如果nums.length%k=0,也就是数组长度为k的倍数,这个会原地打转,如下图所示

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

对于这个问题我们可以使用一个数组visited表示这个元素有没有被访问过,如果被访问过就从他的下一个开始,防止原地打转。

 1public static void rotate(int[] nums, int k) {
2    int hold = nums[0];
3    int index = 0;
4    int length = nums.length;
5    boolean[] visited = new boolean[length];
6    for (int i = 0; i < length; i++) {
7        index = (index + k) % length;
8        if (visited[index]) {
9            //如果访问过,再次访问的话,会出现原地打转的现象,
10            //不能再访问当前元素了,我们直接从他的下一个元素开始
11            index = (index + 1) % length;
12            hold = nums[index];
13            i--;
14        } else {
15            //把当前值保存在下一个位置,保存之前要把下一个位置的
16            //值给记录下来
17            visited[index] = true;
18            int temp = nums[index];
19            nums[index] = hold;
20            hold = temp;
21        }
22    }
23}

总结

这题使用前两种方式是最容易想到的,也是比较简单的,第3种方式也容易想到,但操作起来可能稍微有点难度。

标签: 数组
491,回溯算法解将数组拆分成斐波那契序列
« 上一篇
返回列表
下一篇 »
发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表
你会是第一个来这里评论的人吗?
最近发布资讯
更多