LeetCode (二) 旋转数组

旋转数组

题目链接
代码链接

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

分析：

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

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

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

思路一：

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

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

思路二：

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

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 规律性的大小变化

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
        }
}

思路三 优化：

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

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