LeetCode -Hot100 - 56. 合并区间

前言

本专栏主要通过“LeetCode 热题100”，来捡起自己本科阶段的算法知识与技巧。语言主要使用c++/java。如果同样正在练习LeetCode 热题100的朋友欢迎关注或订阅本专栏。有疑问欢迎留言交流~

题目描述

题目链接

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

提示：
1 <= nums.length <= 105
-2^31 <= nums[i] <= 2^31 - 1
0 <= k <= 105

思路

解法一： 第一个思路想到的是直接利用现成的vector方法去实现，关键就是删除最后一个元素，然后插入到第一个元素中。代码如下：

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k = k % n; // 防止k大于n的情况，这样可以避免不必要的旋转
        for (int i = 0; i < k; ++i) {
            int temp = nums.back(); // 获取最后一个元素
            nums.pop_back(); // 删除最后一个元素
            nums.insert(nums.begin(), temp); // 在第一个位置插入该元素
        }
    }
};

提交，超出时间限制（看来还是不能投机取巧，不是）。原因很简单vector本质上还就是一个普通的动态数组，数据结构第一节将数组与链表的时候就讲过，list和数组的区别（一个方便插入，一个方便检索）。

解法二： 那第二个解法就是使用现成的list做法。但是既然改作list了，就不要去像上面一样，一个一个去删除，增加元素了.我们可以直接选取后面那一截链表，直接插到前面去。c++ 提供现成的双向链表list类。这边我也整理了 一些常用的list方法。有兴趣的朋友可以查看。list方法代码如下：

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        if (n == 0) return;
        k = k % n; // 防止k大于n的情况，这样可以避免不必要的旋转
        
        // 将数组转换为链表
        list<int> linkedList(nums.begin(), nums.end());
        
        // 将链表的后k个元素移动到前面
        auto it = linkedList.end();
        advance(it, -k);  // 定位到倒数第k个元素
        linkedList.splice(linkedList.begin(), linkedList, it, linkedList.end());
        
        // 将链表转换回数组
        nums.assign(linkedList.begin(), linkedList.end());
    }
};

解法三：开辟一个新数组，去找其中的对应关系。直接复制一个数组。然后找出其中的一一对应关系即可。代码如下：

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k = k % n; // 防止k大于n的情况
        vector<int> copynums(nums);
        for (int i=0; i<n; ++i){
            nums[i] = copynums[(n-k+i)%n];
        }
    }
};