C++实现LeetCode(189.旋转数组)

[LeetCode] 189. Rotate Array 旋转数组

Given an array, rotate the array to the right by k steps, where k is non-negative.

Example 1:

Input:

[1,2,3,4,5,6,7]

and k = 3

Output:

[5,6,7,1,2,3,4]

Explanation:

rotate 1 steps to the right:

[7,1,2,3,4,5,6]

rotate 2 steps to the right:

[6,7,1,2,3,4,5]

rotate 3 steps to the right:

[5,6,7,1,2,3,4]

Example 2:

Input:

[-1,-100,3,99]

and k = 2
Output: [3,99,-1,-100]
Explanation:
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]

Note:

  • Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
  • Could you do it in-place with O(1) extra space? 

新题抢先刷,这道题标为 Easy,应该不是很难,我们先来看一种 O(n) 的空间复杂度的方法,我们复制一个和 nums 一样的数组,然后利用映射关系 i -> (i+k)%n 来交换数字。代码如下:

解法一:

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

由于提示中要求我们空间复杂度为 O(1),所以我们不能用辅助数组,上面的思想还是可以使用的,但是写法就复杂的多,而且需要用到很多的辅助变量,我们还是要将 nums[idx] 上的数字移动到 nums[(idx+k) % n] 上去,为了防止数据覆盖丢失,我们需要用额外的变量来保存,这里用了 pre 和 cur,其中 cur 初始化为了数组的第一个数字,然后当然需要变量 idx 标明当前在交换的位置,还需要一个变量 start,这个是为了防止陷入死循环的,初始化为0,一旦当 idx 变到了 strat 的位置,则 start 自增1,再赋值给 idx,这样 idx 的位置也改变了,可以继续进行交换了。举个例子,假如 [1, 2, 3, 4], K=2 的话,那么 idx=0,下一次变为 idx = (idx+k) % n = 2,再下一次又变成了 idx = (idx+k) % n = 0,此时明显 1 和 3 的位置还没有处理过,所以当我们发现 idx 和 start 相等,则二者均自增1,那么此时 idx=1,下一次变为 idx = (idx+k) % n = 3,就可以交换完所有的数字了。

因为长度为n的数组只需要更新n次,所以我们用一个 for 循环来处理n次。首先 pre 更新为 cur,然后计算新的 idx 的位置,然后将 nums[idx] 上的值先存到 cur 上,然后把 pre 赋值给 nums[idx],这相当于把上一轮的 nums[idx] 赋给了新的一轮,完成了数字的交换,然后 if 语句判断是否会变到处理过的数字,参见上面一段的解释,我们用题目中的例子1来展示下面这种算法的 nums 的变化过程:

1 2 3 4 5 6 7
1 2 3 1 5 6 7
1 2 3 1 5 6 4
1 2 7 1 5 6 4
1 2 7 1 5 3 4
1 6 7 1 5 3 4
1 6 7 1 2 3 4
5 6 7 1 2 3 4

解法二:

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        if (nums.empty() || (k %= nums.size()) == 0) return;
        int start = 0, idx = 0, pre = 0, cur = nums[0], n = nums.size();
        for (int i = 0; i < n; ++i) {
            pre = cur;
            idx = (idx + k) % n;
            cur = nums[idx];
            nums[idx] = pre;
            if (idx == start) {
                idx = ++start;
                cur = nums[idx];
            }
        }
    }
};

这道题其实还有种类似翻转字符的方法,思路是先把前 n-k 个数字翻转一下,再把后k个数字翻转一下,最后再把整个数组翻转一下:

1 2 3 4 5 6 7
4 3 2 1 5 6 7
4 3 2 1 7 6 5
5 6 7 1 2 3 4

解法三:

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        if (nums.empty() || (k %= nums.size()) == 0) return;
        int n = nums.size();
        reverse(nums.begin(), nums.begin() + n - k);
        reverse(nums.begin() + n - k, nums.end());
        reverse(nums.begin(), nums.end());
    }
};

由于旋转数组的操作也可以看做从数组的末尾取k个数组放入数组的开头,所以我们用 STL 的 push_back 和 erase 可以很容易的实现这些操作。

解法四:

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

下面这种方法其实还蛮独特的,通过不停的交换某两个数字的位置来实现旋转,根据网上这个帖子的思路改写而来,数组改变过程如下:

1 2 3 4 5 6 7
5 2 3 4 1 6 7
5 6 3 4 1 2 7
5 6 7 4 1 2 3
5 6 7 1 4 2 3
5 6 7 1 2 4 3
5 6 7 1 2 3 4

解法五:

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        if (nums.empty()) return;
        int n = nums.size(), start = 0;
        while (n && (k %= n)) {
            for (int i = 0; i < k; ++i) {
                swap(nums[i + start], nums[n - k + i + start]);
            }
            n -= k;
            start += k;
        }
    }
};

到此这篇关于C++实现LeetCode(189.旋转数组)的文章就介绍到这了,更多相关C++实现旋转数组内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • C++实现LeetCode(60.序列排序)

    [LeetCode] 60. Permutation Sequence 序列排序 The set [1,2,3,...,n] contains a total of n! unique permutations. By listing and labeling all of the permutations in order, we get the following sequence for n = 3: "123" "132" "213" &

  • C++实现LeetCode(61.旋转链表)

    [LeetCode] 61. Rotate List 旋转链表 Given the head of a linked list, rotate the list to the right by k places. Example 1: Input: head = [1,2,3,4,5], k = 2 Output: [4,5,1,2,3] Example 2: Input: head = [0,1,2], k = 4 Output: [2,0,1] Constraints: The number

  • C++实现LeetCode(56.合并区间)

    [LeetCode] 56. Merge Intervals 合并区间 Given a collection of intervals, merge all overlapping intervals. Example 1: Input: [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]] Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into

  • C++实现LeetCode(59.螺旋矩阵之二)

    [LeetCode] 59. Spiral Matrix II 螺旋矩阵之二 Given a positive integer n, generate a square matrix filled with elements from 1 to n2 in spiral order. Example: Input: 3 Output: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ] 此题跟之前那道 Spiral Matrix 本质上没什么区别,就相当于个类似逆

  • C++实现LeetCode(57.插入区间)

    [LeetCode] 57. Insert Interval 插入区间 Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary). You may assume that the intervals were initially sorted according to their start times. Example 1: Input: int

  • C++实现LeetCode(58.求末尾单词的长度)

    [LeetCode] 58. Length of Last Word 求末尾单词的长度 Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string. If the last word does not exist, return 0. Note: A word is defined as a

  • C++实现LeetCode(189.旋转数组)

    [LeetCode] 189. Rotate Array 旋转数组 Given an array, rotate the array to the right by k steps, where k is non-negative. Example 1: Input: [1,2,3,4,5,6,7] and k = 3 Output: [5,6,7,1,2,3,4] Explanation: rotate 1 steps to the right: [7,1,2,3,4,5,6] rotate

  • C语言双指针多方法旋转数组解题LeetCode

    目录 暴力思路 外加数组 格局抬高 环形替代 LeetCode题目如下: 首先这个中等难度我是没搞懂,后面才发现原来中等中在要求多方法上,那就来看看怎么搞定他吧. 暴力思路 首先我说一下我本人的思路,就是函数进行倒序操作,分三步: 1.整体倒序 :1234567-------7654321 2.前半部分倒序:7654321------- 5674321 3.后半部分倒序:5674321-------5671234 由于题目已经给出了我们 k 的值,我们直接暴力思路(注意是暴力思路非暴力求解),双

  • C++中求旋转数组中的最小数字(经典面试题)

    面试题:旋转数组的最小数字 题目:把一个数组的最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转.输入一个递增数组的旋转,输出旋转数组的最小元素.例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1. 算法: (1)当输入的旋转数组非法时:处理! (2)当输入的旋转数组正常时,index1 = 0:index2=length-1: a:如果arry[index1] <arry[index2]时:说明数组为原数组,并没有进行旋转:    b:如果arry[ind

  • 求解旋转数组的最小数字

    求解旋转数组的最小数字 题目描述: 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转.输入一个递增排序的数组的一个旋转,输出旋转数组的最小数组.例如数组{3,4,5,1,2}是数组{1,2,3,4,5}的旋转数组,该数组的最小值为1. 思路解析: O(N)的算法 这种算法的思想就是遍历这个数组,由于这个数组是两部分有序的数组,因此遍历这个数组时当后一个数字小于前一个数字时,则后一个(即较小)一定为整个数组中最小的数字. 这种算法的思想很简单,但就是时间复杂度较大,因此不是很好的算

  • C++实现旋转数组的二分查找

    本文实例讲述了C++实现旋转数组的二分查找方法,分享给大家供大家参考.具体方法如下: 题目要求: 旋转数组,如{3, 4, 5, 1, 2}是{1, 2, 3, 4, 5}的一个旋转,要求利用二分查找查找里面的数. 这是一道很有意思的题目,容易考虑不周全.这里给出如下解决方法: #include <iostream> using namespace std; int sequentialSearch(int *array, int size, int destValue) { int pos

  • 面试题:Java 实现查找旋转数组的最小数字

    在算法面试中,面试官总是喜欢围绕链表.排序.二叉树.二分查找来做文章,而大多数人都可以跟着专业的书籍来做到倒背如流.而面试官并不希望招收的是一位记忆功底很好,但不会活学活用的程序员.所以学会数学建模和分析问题,并用合理的算法或数据结构来解决问题相当重要. 面试题:打印出旋转数组的最小数字 题目:把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转.输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素.例如数组 {3,4,5,1,2} 为数组 {1,2,3,4,5} 的一个旋转,该

  • Python实现的旋转数组功能算法示例

    本文实例讲述了Python实现的旋转数组功能算法.分享给大家供大家参考,具体如下: 一.题目 给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数. 例1: 输入: [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: 输入: [-1,-100,3,99] 和 k = 2 输出

  • C++实现LeetCode(26.有序数组中去除重复项)

    [LeetCode] 26. Remove Duplicates from Sorted Array 有序数组中去除重复项 Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length. Do not allocate extra space for another array, you must do this

  • C++实现LeetCode(80.有序数组中去除重复项之二)

    [LeetCode] 80. Remove Duplicates from Sorted Array II 有序数组中去除重复项之二 Given a sorted array nums, remove the duplicates in-place such that duplicates appeared at most twice and return the new length. Do not allocate extra space for another array, you mus

随机推荐