栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

leetcode 189. 轮转数组

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

leetcode 189. 轮转数组

题目

https://leetcode.cn/problems/rotate-array/

题解 1、暴力遍历

该方法的思想就是 使用一个map暂存一下源数组内的下标和值。然后遍历源数组的时候 从map中取值赋值。代码如下

public void rotate(int[] nums, int k) {
        int n = nums.length;
        k = k % n;
        if (k != 0 && n > 1) {
            Map map = new HashMap<>();
            int j = n - k;
            for (int i = 0; i < n; i++) {
                map.put(i, nums[i]);
                if (j < n) {
                    map.put(j, nums[j]);
                    j++;
                }
                nums[i] = i < k ? map.get(n - k + i) : map.get(i - k);
            }
        }
    }

这是本人没看题解自己做出来的。后来一对比题解果然感觉自己还是太菜了。击败了11%的用户 o(╥﹏╥)o

2、额外数组

顾名思义 就是将源数组的值按照规则添加到新数组 最后再将新数组的值复制到源数组。代码如下

    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k = k % n;
        int[] newNums = new int[n];
        for (int i = 0; i < n; i++) {
            newNums[(i + k) % n] = nums[i];
        }
        System.arraycopy(newNums, 0, nums, 0, n);
    }
3、数组翻转

给定nums=[1 2 3 4 5 6 7],k=3,根据题意 处理完成之后数组应该是[5 6 7 1 2 3 4]。不难看出 实际上就是把源数组的后k个元素 移动到了最前面。我们这里可以使用翻转数组的方式:

  1. 将整个数组翻转
  2. 将num[0] 到 nums[k-1]翻转
  3. 将nums[k]到nums[n-1]翻转

代码如下

    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k = k % n;
        reverse(nums, 0, n-1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, n - 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++;
            end--;
        }
    }
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/976204.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号