leetcode189. 轮转数组

这篇具有很好参考价值的文章主要介绍了leetcode189. 轮转数组。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目:

给定一个整数数组 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]

思路:

按下标输出压入新数组,最后赋值到原数组。

代码

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        vector<int> ans;
        int n = nums.size();
        k %= n;
        for(int i = n-k; i < n; i++){
            ans.push_back(nums[i]);
        }
        for(int i = 0; i < n-k; i++){
            ans.push_back(nums[i]);
        }
        for(int i = 0; i < n; i++){
            nums[i] = ans[i];
        }
    }
};

运行结果:

leetcode189. 轮转数组,LeetCode,算法,数据结构

 (这耗费的内存也太多了吧 = = )

答案思路3:【数组翻转】

该方法基于如下的事实:当我们将数组的元素向右移动 kkk 次后,尾部 k mod nk\bmod nkmodn 个元素会移动至数组头部,其余元素向后移动 k mod nk\bmod nkmodn 个位置。

该方法为数组的翻转:我们可以先将所有元素翻转,这样尾部的 k mod nk\bmod nkmodn 个元素就被移至数组头部,然后我们再翻转 [0,k mod n−1][0, k\bmod n-1][0,kmodn−1] 区间的元素和 [k mod n,n−1][k\bmod n, n-1][kmodn,n−1] 区间的元素即能得到最后的答案。

我们以 n=7n=7n=7,k=3k=3k=3 为例进行如下展示:

leetcode189. 轮转数组,LeetCode,算法,数据结构

代码:

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k %= n;
        for (int i = 0; i < n / 2; i++) {
            int temp = nums[i];
            nums[i] = nums[n - 1 - i];
            nums[n - 1 - i] = temp;
        }
        // 翻转前部分元素
        for (int i = 0; i < k / 2; i++) {
            int temp = nums[i];
            nums[i] = nums[k - 1 - i];
            nums[k - 1 - i] = temp;
        }
        // 翻转后部分元素
        for (int i = k; i < k+(n-k)/2; i++) {
            int temp = nums[i];
            nums[i] = nums[n - 1 - i + k];
            nums[n - 1 - i + k] = temp;
        }
    }
};

 运行结果:

leetcode189. 轮转数组,LeetCode,算法,数据结构

 文章来源地址https://www.toymoban.com/news/detail-681829.html

到了这里,关于leetcode189. 轮转数组的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【LeetCode-中等题】189. 轮转数组

    思路:通过,开辟数组 取模运算寻找新位置------ 位置(i+k)mod n =新位置 思路: 1、先全部翻转 2、在根据k 的值 对k-1 的两边区域进行翻转 3、注意 k如果 数组长度 就会出现下标越界,所以需要开始就k对数组长度取模 k %=n

    2024年02月11日
    浏览(32)
  • 【LeetCode】189. 轮转数组 - 双指针

    189. 轮转数组

    2024年02月13日
    浏览(38)
  • 【LeetCode力扣】189 53 轮转数组 | 最大子数组和

    目录 1、189. 轮转数组 1.1、题目介绍 1.2、解题思路 2、53. 最大子数组和 2.1、题目介绍 2.2、解题思路   原题链接: 189. 轮转数组 - 力扣(LeetCode) ​ 示例 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] 向右轮转

    2024年02月08日
    浏览(37)
  • leetcode每日一题——189.轮转数组(面试经典150题)

    189. 轮转数组 - 力扣(LeetCode) 给定一个整数数组  nums ,将数组中的元素 向右轮转  k   个位置 ,其中  k   是非负数。 示例1: 示例2: 1 = nums.length = 105 -231 = nums[i] = 231 - 1 0 = k = 105        对题目进行分析可知,我们需要根据轮转量k,将数组后面的k个元素按照原来的顺

    2024年02月12日
    浏览(39)
  • (C语言版)力扣(LeetCode)189. 轮转数组官方3种解法分析

    题目链接:轮转数组 给定一个整数数组 nums,将数组中的元素向右轮转 k 个位置,其中 k 是非负数。 示例 1: 示例 2: 提示: 1 = nums.length = 105 -231 = nums[i] = 231 - 1 0 = k = 105 进阶: 尽可能想出更多的解决方案,至少有 三种 不同的方法可以解决这个问题。 你可以使用空间复杂度为

    2024年02月05日
    浏览(42)
  • 【数据结构】--189.轮转数组

    💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤 📃 个人主页 :阿然成长日记 👈点击可跳转 📆 个人专栏: 🔹数据结构与算法🔹C语言进阶 🚩 不能则学,不知则问,耻于问人,决无长进 🍭 🍯 🍎 🍏 🍊 🍋 🍒 🍇 🍉 🍓 🍑 🍈 🍌 🍐 🍍 🌸 hello大家好✨又见

    2024年02月15日
    浏览(32)
  • 数据结构与算法之数组: Leetcode 605. 种花问题 (Typescript版)

    种花问题 https://leetcode.cn/problems/can-place-flowers/ 描述 假设有一个很长的花坛,一部分地块种植了花,另一部分却没有。可是,花不能种植在相邻的地块上,它们会争夺水源,两者都会死去。 给你一个整数数组 flowerbed 表示花坛,由若干 0 和 1 组成,其中 0 表示没种植花,1 表示

    2024年02月02日
    浏览(45)
  • 数据结构与算法之数组: Leetcode 89. 格雷编码 (Typescript版)

    格雷编码 https://leetcode.cn/problems/gray-code/ 描述 n 位格雷码序列 是一个由 2n 个整数组成的序列,其中: 每个整数都在范围 [0, 2n - 1] 内(含 0 和 2n - 1) 第一个整数是 0 一个整数在序列中出现 不超过一次 每对 相邻 整数的二进制表示 恰好一位不同 ,且 第一个 和 最后一个 整数

    2024年02月02日
    浏览(43)
  • 数据结构与算法之数组: Leetcode 914. 卡牌分组 (Typescript版)

    卡牌分组 https://leetcode.cn/problems/x-of-a-kind-in-a-deck-of-cards/ 描述 给定一副牌,每张牌上都写着一个整数。 此时,你需要选定一个数字 X,使我们可以将整副牌按下述规则分成 1 组或更多组: 每组都有 X 张牌。 组内所有的牌上都写着相同的整数。 仅当你可选的 X = 2 时返回 true。

    2024年02月02日
    浏览(43)
  • 189. 轮转数组 Python

    给定一个整数数组 nums ,将数组中的元素向右轮转 k 个位置,其中 k 是非负数。 示例 1 示例 2 提示: 1 = nums.length = 10^5 -2^31 = nums[i] = 2^31 - 1 0 = k = 10^5 代码如下: 本题题意很简单,实际上需要操作的是将已知数组nums的后k位给挪到nums数组的首部且保证是原地修改。本题解采用

    2024年02月12日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包