初级算法-数组-旋转数组

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

进阶：
尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？

摘一个示例做个说明.
示例 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]
提示：
1 <= nums.length <= 2 * 104
-231 <= nums[i] <= 231 - 1
0 <= k <= 105

条件分析:

1. 数组向右移动k位,k 是非负数 -> k是非负数,
2. 0 <= k <= 105 -> k可能比较大

解决思路1:

1. 根据分析1、2,k可能为0或者非常大.

以此说明,k可能是能循环数组好几圈的,所以需要对k取余.找出当前数据旋转后的位置,然后用新数组去承接转换后的数据.

解决思路2:

旋转数组,说明数据不变,只是改变位置.可以想象成一个圆环,进行转圈操作

如果数组是环形的话,我们直接旋转就行了.怎么实现数组环形类型的操作呢?因为数据是右移k位,所以实际移动的位置是k余.所以采用翻转,先翻转数组,在翻转旋转点前的和旋转点后的即可

解决思路3:

旋转数据,说明数据不变,只是改变位置.可以想象成数组后面的数据跑到前面了

找到k余,然后将后面的数据依次添加到起始位置,然后删除最后一个即可.

解决思路4:

根据思路2延伸,不用翻转数组.说明我们需要将起始数据挪到旋转后的位置,然后将该位置的数据挪到对应旋转后的位置.直到每个数据都被循环一次.即通过找k和数组长度的最大公约数,这样能确定循环几次才能完成.然后循环进行替换.直到遍历完成

首先找k和nums长度的最大公约数,获取需要循环的圈数.以保证每个数据都被循环一次.然后找到每次旋转后的位置,进行数据交换.再交换该位置的数据到对应相应的位置,直到结束

代码实现-Swift版本:

思路1代码:

func rotate(_ nums: inout [Int], _ k: Int) {
    if k % nums.count == 0 || nums.count == 1{
        return
    }
    var array = nums
    // 采用新数组去承接,然后求余位置,赋值到新数组
    for i in 0 ..< nums.count {
        array[(i + k) % nums.count] = nums[i]
    }
    nums = array
}

旋转数组 1 提交结果.jpg

思路2代码:

func rotate(_ nums: inout [Int], _ k: Int) {
    if k % nums.count == 0 || nums.count == 1{
        return
    }
    // 翻转整个数组
    nums.reverse()
    // 翻转旋转点前的,这样数据就双翻回正
    nums[0 ..< k % nums.count].reverse()
    // 翻转旋转点后到,数据双翻回正
    nums[k % nums.count ..< nums.count].reverse()
}

旋转数组 2 提交结果.jpg

思路3代码:

func rotate(_ nums: inout [Int], _ k: Int) {
    if k % nums.count == 0 || nums.count == 1{
        return
    }
    // 获取旋转点,然后数组最后的数据依次添加到前面即可
    for _ in 0 ..< k % nums.count {
        nums.insert(nums.last!, at: 0)
        nums.removeLast()
    }
    
    print(nums)
}

旋转数组 3 提交结果.jpg

思路4代码:

func rotate(_ nums: inout [Int], _ k: Int) {
    if k % nums.count == 0 || nums.count == 1{
        return
    }
    // 获取需要循环的次数
    let count = gcd(k, nums.count)
    
    for i in 0 ..< count {
        // 获取当前索引
        var current = i
        repeat{
            // 获取旋转后的位置
            let next = (current + k) % nums.count
            // 交换位置
            nums.swapAt(next, i)
            current = next
            
        }while i != current
    }
    
    print(nums)
}

// 最大公约数
func gcd(_ a :Int ,_ b :Int) -> Int {
    
    if a == b {//如果两个数相等.则直接返回
        return a
    }
    let big = max(a, b)
    let small = min(a, b)
    
    var divi = 0
    for i in 1..<small+1 {//选出两个数中较小的那个数将其分解因数
        if small % i  == 0{
            divi = small/i  //分解因子,因为是从1到small遍历.所以i 为较小的那个 ,divi为较大的那个
            if big%divi == 0{//判断divi能否被较大的那个数整除,如果能则divi是最大公约数
                return divi
            }
        }
    }
    return 1
}

旋转数组 4 提交结果.jpg

测试用例:

// 数组元素为最小一个,且k不为0
var nums0: [Int] = [1]
let k = 4
// 数组元素为最小一个,且k为0
var nums1: [Int] = [1]
let k = 0
// 数组元素为两个,且k不为0
var nums2: [Int] = [1,3]
let k = 24
// 数组元素为两个,且k为0
var nums3: [Int] = [1,3]
let k = 0
// 数组元素为多个,且k不为0
var nums4: [Int] = [1,2,3,4,5,6,7,8,9,10,11,12,13]
let k = 1024
// 数组元素为多个,且k为0
var nums5: [Int] = [1,2,3,4,5,6,7,8,9,10,11,12,13]
let k = 0

考察要点:

• 数组
• 数学
• 双指针