旋转数组(初级算法)——多种方法求解

本文主要是介绍旋转数组(初级算法)——多种方法求解，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目：
给定一个数组，将数组中的元素向右移动 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 <= 2 * 104
-231 <= nums[i] <= 231 - 1
0 <= k <= 105

解题方式：
方法一：使用额外的数组
我们可以使用额外的数组来将每个元素放至正确的位置。用 n 表示数组的长度，然后我们遍历原数组，将原数组下标为 i 的元素放至新数组下标为 ：(i+k) mod n的位置，最后将新数组拷贝至原数组即可（取余作用：防止数越界）。

//c++的解决方法函数
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());
}

//c的解决方法函数
void rotate(int* nums, int numsSize, int k) {
    int newArr[numsSize];
    for (int i = 0; i < numsSize; ++i) {
        newArr[(i + k) % numsSize] = nums[i];
    }
    for (int i = 0; i < numsSize; ++i) {
        nums[i] = newArr[i];
    }
}

方法二：粗暴好理解，常规做法
第一步：我们首先将需要移动的元素放入一个新的数组，
第二步：然后移动给定的原数组元素使其满足条件，
第三步：最后将最开始移动的元素从新的数组中，放入原来数组的开的头。
该方法内存占用较大

//c解决方法
void rotate(int* nums, int numsSize, int k){
    k %= numsSize;
    int R_k = k,j=0;
    int num[numsSize];
    for(int i = numsSize-1; R_k > 0; R_k--){
        num[j++] = nums[i--];
    }
    R_k = k;
    for(int i = numsSize-1-R_k; i >= 0; i-- ){ 
        nums[i+k] = nums[i];
    }
    R_k = k;
    for(int i = R_k-1,j=0; i >= 0; i--){
        nums[j++] = num[i];
    }
}

附加知识点c++的vector：

一、什么是vector？
向量（Vector）是一个封装了动态大小数组的顺序容器（Sequence Container）。跟任意其它类型容器一样，它能够存放各种类型的对象。可以简单的认为，向量是一个能够存放任意类型的动态数组。
二、基本函数实现
1>构造函数：

1. vector():创建一个空vector
2. vector(int nSize):创建一个vector,元素个数为nSize
3. vector&):复制构造函数 vector(begin,end):复制[begin,end)区间内另一个数组的元素到vector中

2> 增加函数

1. void push_back(const T& x):向量尾部增加一个元素X
2. iterator insert(iterator it,const T& x):向量中迭代器指向元素前增加一个元素x
3. iterator insert(iterator it,int n,const T& x):向量中迭代器指向元素前增加n个相同的元素x

3>删除元素

1. iterator erase(iterator it):删除向量中迭代器指向元素

4>判断是否为空

1. bool empty() const:判断向量是否为空，若为空，则向量中无元素

5>迭代器中的元素个数

1. int size() const:返回向量中元素的个数

更多vector知识请参考：
https://www.runoob.com/w3cnote/cpp-vector-container-analysis.html

这篇关于旋转数组(初级算法)——多种方法求解的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！