LeetCode (二) 旋转数组

旋转数组

题目链接
代码链接

给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。
尽可能相处更多的解决方案,至少有三种不同的方法可以解决这个问题;
要求使用空间复杂度为 O(1) 的原地算法

分析:

这道题是数组元素移动问题,如果想要达到较好的性能:

  1. 空间复杂度
  2. 时间复杂度(尽量不要触动数组的整体移动)

除此之外,还有就是交换的问题,

思路一:

直接复制一份数组,然后做一下交换

1
2
3
4
5
6
7
8
var numbers = [1,2,3,4,5,6,7]
var k = 3
var numberCopy = numbers
for i in 0 ..< numbers.count {
numberCopy[(k + i) % numbers.count] = numbers[i]
}

numberCopy

思路二:

这种操作,相对来说比较好理解,就是一步一步进行原地置换,但是时间复杂度较高,因为没有个数字的交换都牵扯数组整体数据交换,但是作为理解还是可以实际操作一波的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var  count = numbers.count
var start = 0
k = k % count
for _ in 0 ..< k {

for i in 0 ..< count - 1 {
numbers[count - i - 1] = numbers[count - i-1] ^ numbers[(count - i) % count]
numbers[(count - i) % count] = numbers[(count - i) % count] ^ numbers[count - i-1]
numbers[count - i - 1] = numbers[count - i-1] ^ numbers[(count - i) % count]

}
}

numbers

思路三:

实现数组内数据的交换,只要找到交换规律,就可以实现效率较高的算法。
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

func swapNumbers<T>(_ nums: inout Array<T>, _ p: Int, _ q: Int) {
(nums[p], nums[q]) = (nums[q], nums[p])
}
numbers = [1,2,3,4,5,6,7]

func rotate(_ nums: inout [Int], _ k: Int) {
var count = nums.count
var start = 0
var vk = k
vk = vk % count
while count > 0 && vk > 0{
for i in 0 ..< vk {
// i + start count - vk + i + start
swapNumbers(&nums, i + start, count-vk+i + start)
}
count = count - vk
start = start + vk
vk = vk % count
}
}

思路三 优化:

使用系统自带的数组交换元素函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func rotate(_ nums: inout [Int], _ k: Int) {
var count = nums.count
var start = 0
var vk = k
vk = vk % count
while count > 0 && vk > 0{
for i in 0 ..< vk {
// i + start count - vk + i + start
nums.swapAt(i + start, count-vk+i + start)
}
count = count - vk
start = start + vk
vk = vk % count
}
}

执行结果:

参考:

https://www.cnblogs.com/grandyang/p/4298711.html

-------------本文结束谢谢欣赏-------------
Alice wechat