数据结构之顺序移动数组(巧似数学逆矩阵原理)原理描述

在复习数据结构的时候学习到关于线性表的操作题,答案解析非常有趣

题目大意是:给定一个数组,要求把数组的元素依次向后面序号移动,溢出的元素依次填充到原来被移动的元素的位置,具体要求如图所示

例:

序号 0 1 2 3 4 5 6
元素 1 2 3 4 5 6 7

按要求变化得到如下(如要求循环移动4个)

序号 0 1 2 3 4 5 6
元素 4 5 6 7 1 2 3

解体思路:

一、我的思路

  把循环移动当成元素之间的互换。

  首先,由需要循环移动的位置数确定需要移动的元素的个数;

  其次,找到同一元素值在移动前后的坐标值之间的数量关系;

  最后,通过循环完成位置值之间的交换。

  时间复杂度 O(n),空间复杂度为O(1)

二、王道的解题思路

  将原数组看成两个数组(一个需要是向后移动的数据元素,一个是溢出后补充到前面的数组元素),利用逆运算进行运算

  原理过程与线性代数的矩阵的逆运算极为相似(并不是真正的存放到两个数组变量中实现)

  将数组看成  AB===>对两个数组进行逆序得到  A-1B-1

  然后将两个数组合成一个整体进行逆序得到BA

一腔孤勇,淡然且快乐。
原文地址:https://www.cnblogs.com/withheart1202-never/p/13628633.html