`
SunnyYoona
  • 浏览: 361691 次
社区版块
存档分类
最新评论

[LeetCode]189.Rotate Array

 
阅读更多

题目

Rotate an array of n elements to the right by k steps.

For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].

Note:
Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.

Hint:
Could you do it in-place with O(1) extra space?

思路一

跟字符串左右旋转操作一样的思路。
三次翻转法,第一次翻转前n-k个,第二次翻转后k个,第三次翻转全部。

代码一

    /*--------------------------------------------
    *   日期:2014-02-25
    *   作者:SJF0115
    *   题目: 189.Rotate Array
    *   网址:https://oj.leetcode.com/problems/rotate-array/
    *   结果:AC
    *   来源:LeetCode
    *   博客:
    ------------------------------------------------*/
    #include <iostream>
    #include <stdio.h>
    using namespace std;

    class Solution {
    public:
        void rotate(int nums[], int n, int k) {
            if(n <= 1){
                return;
            }//if
            k = k % n;
            if(k <= 0){
                return;
            }//if
            // 翻转前n-k个
            Reverse(nums,0,n - k - 1);
            // 翻转后k个
            Reverse(nums,n - k,n - 1);
            // 翻转全部
            Reverse(nums,0,n - 1);
        }
    private:
        void Reverse(int nums[],int left,int right){
            int tmp;
            for(int i = left,j = right;i < j;++i,--j){
                // 交换
                swap(nums[i],nums[j]);
            }//for
        }
    };
    int main() {
        Solution solution;
        int A[] = {1,2,3,4,5,6,7};
        int n = 7;
        int k = 2;
        solution.rotate(A,n,k);
        for(int i = 0;i < n;++i){
            cout<<A[i]<<" ";
        }//for
        cout<<endl;
        return 0;
    }

思路二

充分利用Cycle Sort(圈排序)思路。

一个环总是要回到原来的位置。这与K和N的最小公倍数有关。 P步之后当PK== QN == LCM时环遍历完成。

  • 我们可以很容易地看出,P <= N;
  • 如果P是N的因子,这意味着该程序有N/P个环;
  • 证明上面结论:p和q的最大公约数为1,p为q* n的因子,因此p是n的因子。

这里写图片描述
这里写图片描述

代码二

    /*--------------------------------------------
    *   日期:2014-02-25
    *   作者:SJF0115
    *   题目: 189.Rotate Array
    *   网址:https://oj.leetcode.com/problems/rotate-array/
    *   结果:AC
    *   来源:LeetCode
    *   博客:
    ------------------------------------------------*/
    #include <iostream>
    #include <stdio.h>
    using namespace std;

    class Solution {
    public:
        void rotate(int nums[], int n, int k) {
            if (n <= 0){
                return;
            }//if
            k = k % n;
            if (k <= 0) {
                return;
            }//if
            int cycle = 0;
            int next = 0;
            int tmp = nums[next];
            for ( int i = 0; i< n; i++) {
                next = (next + k) % n;
                swap(nums[next], tmp);
                // 如果一圈转完,向前移动一步
                if (cycle == next) {
                    next ++;
                    cycle = next;
                    tmp = nums[next];
                }//if
            }//for
        }
    };
    int main() {
        Solution solution;
        int A[] = {1,2,3,4,5,6,7};
        int n = 7;
        int k = 2;
        solution.rotate(A,n,k);
        for(int i = 0;i < n;++i){
            cout<<A[i]<<" ";
        }//for
        cout<<endl;
        return 0;
    }

相似题目:

LeetCode之Rotate List

[经典面试题]完美洗牌算法

<script type="text/javascript"> $(function () { $('pre.prettyprint code').each(function () { var lines = $(this).text().split('\n').length; var $numbering = $('<ul/>').addClass('pre-numbering').hide(); $(this).addClass('has-numbering').parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($('<li/>').text(i)); }; $numbering.fadeIn(1700); }); }); </script>
分享到:
评论

相关推荐

    LeetCode最全代码

    26 | [Remove Duplicates from Sorted Array](https://leetcode.com/problems/remove-duplicates-from-sorted-array/)| [C++](./C++/remove-duplicates-from-sorted-array.cpp) [Python](./Python/remove-duplicates...

    leetcode答案-LeetCode:LeetCode刷题记录,README显示实时进度/题目

    189.rotate-array.js /* * @lc app=leetcode id=189 lang=javascript * * [189] Rotate Array * * https://leetcode.com/problems/rotate-array/description/ * * algorithms * Easy (28.74%) * Total Accepted: 262...

    扔鸡蛋leetcode-LeetCode-Note-Mary:玛丽的leetcode笔记本

    Rotate Array (旋转数组) #数组 33. Search in Rotated Sorted Array(搜索旋转排序数组)#数组 2020/12/08 19. Remove Nth Node From End of List(删除链表的倒数第N个节点) 153. Find Minimum in Rotated Sorted...

    戳气球leetcode-leetcode:leetcode

    189.rotate-array 283.move-zero Range Sum Query - Immutables 66.Plus One 快手-跳格子 Intersection of Two Arrays 17.10. Find Majority Element LCCI Game of Life Find All Numbers Disappeared in an Array ...

    leetcode跳跃-leetcode:leetcode解题之路

    旋转图像](./Array/rotate-image.md) Heap 堆 [0023 合并K个排序链表](./Heap/merge-k-sorted-lists.md) String 字符串 [0006 Z字形变换](./String/zigzag-conversion.md) [0030 串联所有单词的子串](./String/...

    leetcode添加元素使和等于-LeetCodeNotes:力码笔记

    leetcode添加元素使和等于 LeetCodeNotes Array: 4. Median of Two Sorted Arrays 思路: 基于二分查找的思想 88. Merge Sorted Array 描述:合并两个有序数组,将B合并入A,A长度刚好为A.length + B.length nums1 =...

    leetcode1004-leetcode:leetcode

    Rotate Image (M) -&gt; 2 73. Set Matrix Zeroes (M) 1. Two Sum (E) 167. Two Sum II - Input array is sorted (E) 653. Two Sum IV - Input is a BST (E) -&gt; 2 26. Remove Duplicates from Sorted Array (E) 27. ...

    leetcode中国-DP:DP

    leetcode中国大批 0. Count Prime 1. Reverse the array 2. Find the maximum and minimum element in an array 3. Find the "Kth" max and min element of an array 4. Given an array which consists of only 0, 1...

    javalruleetcode-LeetCode:LeetCode算法问题

    RotateList LeetCode 75 Sort Colors LeetCode 125 Valid Palindrome LeetCode 167 Two Sum II - Input array is sorted LeetCode 344 Reverse String LeetCode 345 Reverse Vowels of a String 2 字符串 编号 题目 ...

    lrucacheleetcode-leetcode:记录自己的leetcode解题历程~Welcomeeveryonetocomment:grinning_face:~

    Rotate Image 344. Reverse String 414. Third Maximum Number 448. Find All Numbers Disappeared in an Array 66. Plus One 238. Product of Array Except Self 697. Degree of an Array 849. Maximize ...

    javalruleetcode-LeetCode::lollipop:个人LeetCode习题解答仓库-多语言

    java lru leetcode :ice_cream: LeetCode Kindem 的个人 LeetCode 题解仓库,欢迎交流学习。 下面的目录中 ...Rotate Image 53 Maximum Subarray 55 Jump Game 56 Merge Intervals 64 Minimum Path Sum 73

    gasstationleetcode-LeetCode_Practice:我的LeetCode练习从2020年开始

    189_Rotate_array 41_First_Missing_Positive 299_Bulls_and_Cows 134_Gas_Station 118_Pascal's_Triangle_I 119_Pascal's_Triangle_II 169_Majority_Element 229_Majority_Element_II 274_H_索引 275_H_Index_II ...

    Coding Interview In Java

    1 Rotate Array in Java 15 2 Reverse Words in a String II 19 3 Evaluate Reverse Polish Notation 21 4 Isomorphic Strings 25 5 Word Ladder 27 6 Word Ladder II 29 7 Median of Two Sorted Arrays 33 8 Kth ...

    leetcode中国-Final450_Data-Structures:Final450_数据结构

    leetcode中国Final450_数据结构 实际上,这个存储库包含成为优秀竞争程序员最重要的数据结构和算法。 他们的名字是: Questions ----------- *Reverse the array *Find the maximum and minimum element in an array...

    蓄水池算法leetcode-leetcode:leetcode

    rotate: A Linear Time Majority Vote Algorithm 题解: Maximum Gap: Something about largest-rectangle-in-histogram: 最长递增子序列: 最长公共自序列: Something about: best time to buy and sell stack: ...

    leetcode浇花-LCSolutions:我的力扣解决方案

    leetcode 浇花力扣解决方案 简单的 #0001 - Two Sum #0007 - Reverse Integer #0009 - Palindrome Number #0035 - Search Insert Position #0058 - Length of Last Word #0066 - Plus One #0083 - Remove Duplicates...

    C语言 strcpy和memcpy区别详细介绍

    PS:初学算法,开始刷leetcode,Rotate array的预备知识(写的代码Time Limit Exceed难过)于是百度高效算法,本篇作为预备知识。 1、strcpy和strncpy函数 这个不陌生,大一学C语言讲过,其一般形式为strcpy(字符...

    cpp-算法精粹

    Rotate Array Contains Duplicate Contains Duplicate II Contains Duplicate III Product of Array Except Self Game of Life Increasing Triplet Subsequence 单链表 Reverse Linked List Odd Even Linked List ...

    javalruleetcode-SDE-Problems:标准SDE问题列表

    leetcode SDE-问题 标准 SDE 问题列表 第一天:(数组) 日 问题陈述 解决方案 困难 使用的数据结构 使用的算法 时间复杂度 空间复杂度 补充阅读 在 N 个整数的数组中查找重复项 中等的 大批 不适用 上) O(1) 在不...

Global site tag (gtag.js) - Google Analytics