Java教程

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

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

题目:
给定一个数组,将数组中的元素向右移动 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
在这里插入图片描述

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