面试经典 150 题

文章目录

6、轮转数组

1、描述
给定一个整数数组 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、关键字
数组向后轮转变换
3、思路
先用k对n取模
思路一:使用辅助数组,时间复杂度O(N),空间复杂度O(N)
思路二:发现规律:先把整个数组逆置,之后把前k个元素逆置,之后把后边n- k个元素逆置
4、notes
多练
6、code


class Solution {
public:
   void reverse(vector<int>& nums, int i, int j) {
        while(i < j) {
            int tem = nums[i];
            nums[i] = nums[j];
            nums[j] = tem;     
            i++;
            j--;
        }
   }
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k %= n ;
        reverse(nums, 0, n - 1); // 整个数组逆置
        reverse(nums, 0,  k - 1); // 逆置前边的k个,
        reverse(nums, k, n - 1); // 逆置后边的n - k个
    }
};

相关推荐

  1. 面试经典 150

    2024-07-09 21:42:08       9 阅读
  2. 面试经典150(96-100)

    2024-07-09 21:42:08       37 阅读
  3. 面试经典150(108-110)

    2024-07-09 21:42:08       23 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-09 21:42:08       3 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-09 21:42:08       3 阅读
  3. 在Django里面运行非项目文件

    2024-07-09 21:42:08       2 阅读
  4. Python语言-面向对象

    2024-07-09 21:42:08       2 阅读

热门阅读

  1. MySQL8之mysql-community-common的作用

    2024-07-09 21:42:08       8 阅读
  2. 机器学习综述

    2024-07-09 21:42:08       8 阅读
  3. Qt | Qt常用类列举和说明

    2024-07-09 21:42:08       7 阅读
  4. chatgpt工作原理

    2024-07-09 21:42:08       10 阅读
  5. 在make类构建系统配置文件中定义函数宏

    2024-07-09 21:42:08       6 阅读
  6. lvs集群

    lvs集群

    2024-07-09 21:42:08      8 阅读
  7. 记录Linux安装go环境的一个坑

    2024-07-09 21:42:08       9 阅读
  8. Python开发——Python 字典的使用

    2024-07-09 21:42:08       7 阅读
  9. 流媒体技术

    2024-07-09 21:42:08       10 阅读