旋转数组
给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。
尽可能相处更多的解决方案,至少有三种不同的方法可以解决这个问题;
要求使用空间复杂度为 O(1) 的原地算法
分析:
这道题是数组元素移动问题,如果想要达到较好的性能:
- 空间复杂度
- 时间复杂度(尽量不要触动数组的整体移动)
除此之外,还有就是交换的问题,
思路一:
直接复制一份数组,然后做一下交换
1 | var numbers = [1,2,3,4,5,6,7] |
思路二:
这种操作,相对来说比较好理解,就是一步一步进行原地置换,但是时间复杂度较高,因为没有个数字的交换都牵扯数组整体数据交换,但是作为理解还是可以实际操作一波的:
1 | var count = numbers.count |
思路三:
实现数组内数据的交换,只要找到交换规律,就可以实现效率较高的算法。
k = 3 count = 7
1,2,3,4,5,6,7
numbers[0] <-> numbers[4](7 - 3)
5,2,3,4,1,6,7
numbers[1] <-> numbers[5](7-2)
5,6,3,4,1,2,7
numbers[2] <-> numbers[6](7-1)
5,6,7,4,1,2,3
numbers[3] <-> numbers[7-3]
5,6,7,1,4,2,3
numbers[4] <-> numbers[5](7-2)
5,6,7,1,2,4,3
numbers[5] <-> numbers[5](7-1)
5,6,7,1,2,3,4
从上面可以看出, 前一个角标就是迭代此处,后一个是 k 规律性的大小变化
1 |
|
思路三 优化:
使用系统自带的数组交换元素函数
1 | func rotate(_ nums: inout [Int], _ k: Int) { |