【力扣】189. 轮转数组

文章目录

  • 【力扣】189. 轮转数组
    • 1. 题目介绍
    • 2. 解法
      • 2.1 方法一：不太正规，但是简单
      • 2.2 方法二：使用额外的数组
      • 2.3 方法三：环状替换
      • 2.4 方法四：数组翻转
    • 3. Danger
    • 参考

1. 题目介绍

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

2. 解法

2.1 方法一：不太正规，但是简单

class Solution:def rotate(self, nums: List[int], k: int) -> None:"""Do not return anything, modify nums in-place instead."""k = k % len(nums)for i in range(k):tem = nums.pop()nums.insert(0, tem)return nums

2.2 方法二：使用额外的数组

  • 我们可以使用额外的数组来将每个元素放至正确的位置。用 n 表示数组的长度，我们遍历原数组，将原数组下标为 i 的元素放至新数组下标为(i+k) mod n 的位置，最后将新数组拷贝至原数组即可。
class Solution {public:void rotate(vector<int>& nums, int k) {int n = nums.size();vector<int> newArr(n);for (int i = 0; i < n; ++i) {newArr[(i + k) % n] = nums[i];}nums.assign(newArr.begin(), newArr.end());}};

2.3 方法三：环状替换

  • 需要了解一个定理，环的个数等于：gcd(k, n)
class Solution {public:void rotate(vector<int>& nums, int k) {int n = nums.size();k = k % n;int count = gcd(k, n);for (int start = 0; start < count; ++start) {int current = start;int prev = nums[start];do {int next = (current + k) % n;swap(nums[next], prev);current = next;} while (start != current);}}};

2.4 方法四：数组翻转

class Solution {public:void reverse(vector<int>& nums, int start, int end) {while (start < end) {swap(nums[start], nums[end]);start += 1;end -= 1;}}void rotate(vector<int>& nums, int k) {k %= nums.size();reverse(nums, 0, nums.size() - 1);reverse(nums, 0, k - 1);reverse(nums, k, nums.size() - 1);}};

3. Danger

力扣（LeetCode）是领扣网络旗下专注于程序员技术成长和企业技术人才服务的品牌。源自美国硅谷，力扣为全球程序员提供了专业的IT技术职业化提升平台，有效帮助程序员实现快速进步和长期成长。此外，力扣（LeetCode）致力于解决程序员技术评估、培训、职业匹配的痛点，逐步引领互联网技术求职和招聘迈向专业化。

  • 据了解到的情况，Easy题和Medium 题在面试中比较常见，通常会以手写代码之类的形式出现，您需要对问题进行分析并给出解答，并于面试官进行交流沟通，有时还会被要求分析时间复杂度8与空间复杂度°，面试官会通过您对题目的分析解答，了解您对常用算法的熟悉程度和您的程序实现功底。
  • 而在一些对算法和程序实现功底要求较高的岗位，Hard 题也是很受到面试官的青睐，如果您在面试中成功Bug-Free出一道Hard题，我们相信您一定会给面试官留下很深刻的印象，并极大增加拿到Offer的概率，据相关人士统计，如果您在面试成功解出一道Hard题，拿不到Offer的概率无限接近于0。
  • 所以,力扣中Easy和Medium相当于面试中的常规题，而Hard 则相当于面试中较难的题，解出—道Hard题，Offer可以说是囊中之物。

参考

【1】链接：https://leetcode.cn/problems/rotate-array/ 来源：力扣（LeetCode）