Swift 旋转数组 - LeetCode

旋转数组

将包含 n 个元素的数组向右旋转 k 步。

例如,如果 n = 7 , k = 3,给定数组 [1,2,3,4,5,6,7] ,向右旋转后的结果为 [5,6,7,1,2,3,4]

注意: 尽可能找到更多的解决方案,这里最少有三种不同的方法解决这个问题。

提示: 要求空间复杂度为 O(1)

-1)第一获取最高位的数字,第二把其他位上的数字都抬高一位,第三把最初获得最高位的数字赋值到最低位置上。我觉得这个算法没啥问题啊。。。???可是过不了最后一个测试用例。。。(超出时间限制),好吧。。。希望有大神解惑

代码如下:

class Solution {
    func rotate(_ nums: inout [Int], _ k: Int) {
        var terns = k % nums.count
        if nums.isEmpty || terns == 0 {
            return
        }

        while terns > 0 {
              var temp = 0
              temp = nums.last!
              for i in (0..<(nums.count - 1)).reversed() {
                  nums[i + 1] = nums[i]
              }
              nums[0] = temp
              terns -= 1
        }
    }
}

-2)取余数,比如长度为5的数组,向右旋转2步 1,2,3,4,5 4,5,1,2,3

newNums[(0 + 2) % 5] = nums[0]  即新数组newNums[2] = nums[0] = 1 
newNums[(4 + 2) % 5] = nums[4]  即新数组newNums[1] = nums[4] = 5
...

数字的位置加2之后大于5的都要再从0号位置重新开始计算剩余的步子。这点特性就可以很好的用到求余。 代码如下:

class Solution {
    func rotate(_ nums: inout [Int], _ k: Int) {
        var terns = k % nums.count
        if nums.isEmpty || terns == 0 {
            return
        }
        var newNums = nums
        for i in 0..<nums.count {
            newNums[(i + terns) % nums.count] = nums[i]
        }
        nums = newNums
    }
}

执行时间:28ms

-3)在网上找到一种其他的思路:先把前n-k个数字翻转一下,再把后k个数字翻转一下,最后再把整个数组翻转一下 代码如下:

class Solution {
    func rotate(_ nums: inout [Int], _ k: Int) {
        let terns = k % nums.count
        if nums.isEmpty || terns == 0 {
            return
        }
        let middle = nums.count - terns
        
        reverse(&nums, s: 0, e: middle - 1)
        reverse(&nums, s: middle, e: nums.count - 1)
        reverse(&nums, s: 0, e: nums.count - 1)
    }
    
    func reverse(_ nums: inout [Int], s: Int, e: Int) {
        var s = s
        var e = e
        while s < e {
            let temp = nums[s]
            nums[s] = nums[e]
            nums[e] = temp
            
            s += 1
            e -= 1
        }
    }
}

执行时间:32ms

其他算法,我就不写了。。。。因为不会???

开始用Swift学习算法中,在LeetCode中开始做初级算法这一章节,将做的题目在此做个笔记吧。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器学习从入门到成神

2014百度研发真题及其解析-求比指定数大且最小的“不重复数”

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

15020
来自专栏数据结构与算法

快速排序

快速排序是对冒泡排序的一种改进。它的基本思想是,通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记...

34170
来自专栏轮子工厂

一口气吃下数组的存储方式

Long long ago,我们讲到了数组《聊一聊数组背后的那点事》,这个已经是迈进指针的第一步了,主要的内容是一维数组,今天我们将讲述二维数组。当结束了今天的...

19410
来自专栏好好学java的技术栈

“365算法每日学计划”:05打卡-图解冒泡排序(多解法)

11930
来自专栏老秦求学

题目1054:字符串内排序

题目描述: 输入一个字符串,长度小于等于200,然后将输出按字符顺序升序排序后的字符串。 输入: 测试数据有多组,输入字符串。 输出: 对于每组输入,输出处理后...

34970
来自专栏小樱的经验随笔

UVA 11636-Hello World!(水题,猜结论) UVA11636-Hello World!

UVA11636-Hello World! Time limit: 1.000 seconds When you first made the computer ...

37540
来自专栏小樱的经验随笔

51 Nod 1791 合法括号子段【分治+字符串】

1791 合法括号子段 基准时间限制:1 秒 空间限制:131072 KB 分值: 40 难度:4级算法题 有一个括号序列,现在要计算一下它有多少非空子段是合法...

30860
来自专栏Python小屋

Python版堆排序算法

其他排序算法的Python实现请参考:Python版归并排序算法(附Python程序__name__属性用法演示视频),侏儒排序算法原理与Python实现,Py...

35750
来自专栏desperate633

LintCode 搜索插入位置题目分析代码

给定一个排序数组和一个目标值,如果在数组中找到目标值则返回索引。如果没有,返回到它将会被按顺序插入的位置。 你可以假设在数组中无重复元素。

9230
来自专栏我的技术专栏

数据结构图文解析之:直接插入排序及其优化(二分插入排序)解析及C++实现

18730

扫码关注云+社区

领取腾讯云代金券