【題目描述】
給定一個數(shù)組，將數(shù)組中的元素向右移動 k 個位置屑迂，其中 k 是非負數(shù)浸策。
【示例1】
輸入: [1,2,3,4,5,6,7] 和 k = 3
輸出: [5,6,7,1,2,3,4]
解釋:
向右旋轉(zhuǎn) 1 步: [7,1,2,3,4,5,6]
向右旋轉(zhuǎn) 2 步: [6,7,1,2,3,4,5]
向右旋轉(zhuǎn) 3 步: [5,6,7,1,2,3,4]
【示例2】
輸入: [-1,-100,3,99] 和 k = 2
輸出: [3,99,-1,-100]
解釋:
向右旋轉(zhuǎn) 1 步: [99,-1,-100,3]
向右旋轉(zhuǎn) 2 步: [3,99,-1,-100]
【思路1】
1、暴力解決
2屈糊、每次只移動一個元素的榛，最后移動k%nums.count * num.count次
3、時間復(fù)雜度O(k*n)
4逻锐、空間復(fù)雜度O(1)
Swift代碼實現(xiàn)：
func rotate(_ nums: inout [Int], _ k: Int) {
for _ in 0..<k%nums.count {
let tmp = nums.last!
var lenth = nums.count-1
while lenth > 0 {
nums[lenth] = nums[lenth-1]
lenth-=1
}
nums[0] = tmp
}
}
【思路2】
1夫晌、反轉(zhuǎn)
2雕薪、先把整個數(shù)組倒序排列
3、反轉(zhuǎn)前k-1個元素
4晓淀、再反轉(zhuǎn)k-num.count-1元素
5所袁、時間復(fù)雜度O(n)
6、空間復(fù)雜度O(1)
Swift代碼實現(xiàn)：
func rotate(_ nums: inout [Int], _ k: Int) {
let kk = k%nums.count
rotate(&nums, start: 0, end: nums.count-1)
rotate(&nums, start: 0, end: kk-1)
rotate(&nums, start: kk, end: nums.count-1)
}
func rotate(_ nums:inout [Int],start:Int,end:Int) {
var s = start
var e = end
while s < e {
let tmp = nums[s]
nums[s] = nums[e]
nums[e] = tmp
s+=1
e-=1
}
}
【思路3】
1凶掰、使用額外空間數(shù)組
2燥爷、數(shù)組切片
3、不符合題意
4懦窘、代碼略
