按索引移动数组中的元素
给定n个元素的数组，即
var array = [1, 2, 3, 4, 5]
我可以写一个扩展到Array所以我可以修改数组来实现这个输出： [2, 3, 4, 5, 1] ：
mutating func shiftRight() { append(removeFirst()) }
有没有一种方法可以实现这样一个function，可以将数组按任何索引（正数或负数）进行移位。 我可以使用if-else子句以命令式的风格来实现这个function，但是我正在寻找的是function实现。
该algorithm很简单：
- 将数组拆分成由索引提供的两个
- 将第一个数组附加到第二个数组的末尾
有什么办法来实现它的function风格？
我已经完成的代码：
extension Array { mutating func shift(var amount: Int) { guard -count...count ~= amount else { return } if amount < 0 { amount += count } self = Array(self[amount ..< count] + self[0 ..< amount]) } }
您可以使用范围下标并连接结果。 这会给你你正在寻找的名字，类似于标准库的名字：
extension Array { func shiftRight(var amount: Int = 1) -> [Element] { assert(-count...count ~= amount, "Shift amount out of bounds") if amount < 0 { amount += count } // this needs to be >= 0 return Array(self[amount ..< count] + self[0 ..< amount]) } mutating func shiftRightInPlace(amount: Int = 1) { self = shiftRight(amount) } } Array(1...10).shiftRight() // [2, 3, 4, 5, 6, 7, 8, 9, 10, 1] Array(1...10).shiftRight(7) // [8, 9, 10, 1, 2, 3, 4, 5, 6, 7]
您也可以从shiftRight()返回Array(suffix(count - amount) + prefix(amount))来代替下标。
使用Swift 3，你可以用几行代码创buildshift(withDistance:)和shiftInPlace(withDistance:)方法：
extension Array { func shift(withDistance distance: Int = 1) -> Array<Element> { let offsetIndex = distance >= 0 ? self.index(startIndex, offsetBy: distance, limitedBy: endIndex) : self.index(endIndex, offsetBy: distance, limitedBy: startIndex) guard let index = offsetIndex else { return self } return Array(self[index ..< endIndex] + self[startIndex ..< index]) } mutating func shiftInPlace(withDistance distance: Int = 1) { self = shift(withDistance: distance) } }
用法：
let array1 = Array(1...10) let newArray = array1.shift(withDistance: 3) print(newArray) // prints: [4, 5, 6, 7, 8, 9, 10, 1, 2, 3] var array2 = Array(1...10) array2.shiftInPlace(withDistance: -2) print(array2) // prints: [9, 10, 1, 2, 3, 4, 5, 6, 7, 8] let array3 = Array(1...10) let newArray3 = array3.shift(withDistance: 30) print(newArray3) // prints: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] let array4 = Array(1...10) let newArray4 = array4.shift(withDistance: 0) print(newArray4) // prints: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] var array5 = Array(1...10) array5.shiftInPlace() print(array5) // prints: [2, 3, 4, 5, 6, 7, 8, 9, 10, 1]
我为此尝试了一些扩展。 它有一些很好的function：
- 转移数量大于
count会导致环绕。 - 以负数移动翻转方向
- 以位移二进制运算符（
<<，<<=，>>，>>=）显示>>=
extension Array { func shiftedLeft(by rawOffset: Int = 1) -> Array { let clampedAmount = rawOffset % count let offset = clampedAmount < 0 ? count + clampedAmount : clampedAmount return Array(self[offset ..< count] + self[0 ..< offset]) } func shiftedRight(by rawOffset: Int = 1) -> Array { return self.shiftedLeft(by: -rawOffset) } mutating func shiftLeft(by rawOffset: Int = 1) { self = self.shiftedLeft(by: rawOffset) } mutating func shiftRight(by rawOffset: Int = 1) { self = self.shiftedRight(by: rawOffset) } } //Swift 3 func << <T>(array: [T], offset: Int) -> [T] { return array.shiftedLeft(by: offset) } func >> <T>(array: [T], offset: Int) -> [T] { return array.shiftedRight(by: offset) } func <<= <T>(array: inout [T], offset: Int) { return array.shiftLeft(by: offset) } func >>= <T>(array: inout [T], offset: Int) { return array.shiftRight(by: offset) } /*// Swift 2.2 func << <T>(array: [T], offset: Int) -> [T] { return array.shiftedLeft(by: offset) } func >> <T>(array: [T], offset: Int) -> [T] { return array.shiftedRight(by: offset) } func <<= <T>(inout array: [T], offset: Int) { return array.shiftLeft(by: offset) } func >>= <T>(inout array: [T], offset: Int) { return array.shiftRight(by: offset) }*/
你可以在这里看到它的行动。
下面是一个更通用的解决scheme，它可以为符合要求的任何types实现这个function：
extension RandomAccessCollection where Self: RangeReplaceableCollection, Self.Index == Int, Self.IndexDistance == Int { func shiftedLeft(by rawOffset: Int = 1) -> RangeReplaceableSlice<Self> { let clampedAmount = rawOffset % count let offset = clampedAmount < 0 ? count + clampedAmount : clampedAmount return self[offset ..< count] + self[0 ..< offset] } func shiftedRight(by rawOffset: Int = 1) -> RangeReplaceableSlice<Self> { return self.shiftedLeft(by: -rawOffset) } mutating func shiftLeft(by rawOffset: Int = 1) { self = Self.init(self.shiftedLeft(by: rawOffset)) } mutating func shiftRight(by rawOffset: Int = 1) { self = Self.init(self.shiftedRight(by: rawOffset)) } //Swift 3 static func << (c: Self, offset: Int) -> RangeReplaceableSlice<Self> { return c.shiftedLeft(by: offset) } static func >> (c: Self, offset: Int) -> RangeReplaceableSlice<Self> { return c.shiftedRight(by: offset) } static func <<= (c: inout Self, offset: Int) { return c.shiftLeft(by: offset) } static func >>= (c: inout Self, offset: Int) { return c.shiftRight(by: offset) } }
根据Nate Cook的回答 ，我还需要移动一个返回倒序的数组，所以我做了：
//MARK: - Array extension Array { func shiftRight( amount: Int = 1) -> [Element] { var amountMutable = amount assert(-count...count ~= amountMutable, "Shift amount out of bounds") if amountMutable < 0 { amountMutable += count } // this needs to be >= 0 return Array(self[amountMutable ..< count] + self[0 ..< amountMutable]) } func reverseShift( amount: Int = 1) -> [Element] { var amountMutable = amount amountMutable = count-amountMutable-1 let a: [Element] = self.reverse() return a.shiftRight(amountMutable) } mutating func shiftRightInPlace(amount: Int = 1) { self = shiftRight(amount) } mutating func reverseShiftInPlace(amount: Int = 1) { self = reverseShift(amount) } }
我们有例如：
Array(1...10).shiftRight() // [2, 3, 4, 5, 6, 7, 8, 9, 10, 1] Array(1...10).shiftRight(7) // [8, 9, 10, 1, 2, 3, 4, 5, 6, 7] Array(1...10).reverseShift() // [2, 1, 10, 9, 8, 7, 6, 5, 4, 3] Array(1...10).reverseShift(7) // [8, 7, 6, 5, 4, 3, 2, 1, 10, 9]
这里是“就地”轮换的function实现，不需要额外的内存和临时variables，每个元素只能执行一次交换。
extension Array { mutating func rotateLeft(by rotations:Int) { let _ = // silence warnings (1..<Swift.max(1,count*((rotations+1)%(count+1)%1))) // will do zero or count - 1 swaps .reduce((i:0,r:count+rotations%count)) // i: swap index r:effective offset { s,_ in let j = (s.i+sr)%count // j: index of value for position i swap(&self[j],&self[si]) // swap to place value at rotated index return (j,sr) // continue with next index to place } } }
它优化地支持零，正和负旋转以及比arrays大小和空arrays旋转更大的旋转（即它不能失败）。
使用负值在另一个方向旋转（向右）。
将一个3元素arrays旋转10就像将它旋转1，第一次旋转将使它回到初始状态（但我们不想多次移动元素）。
向右旋转5个元素的数组，即rotateLeft（by：-3）相当于rotateLeft（by：2）。 该函数的“有效偏移量”考虑到了这一点。
在目标C中，你可以像这样简单地得到左移数组：
- (NSMutableArray *)shiftedArrayWithOffset:(NSInteger)offset { NSMutableArray *bufferArray = [[NSMutableArray alloc] initWithArray:originalArray]; for (int i = 0; i < offset; i++) { id object = [bufferArray firstObject]; [bufferArray removeObjectAtIndex:0]; [bufferArray addObject:object]; } return bufferArray; }
最快的方法是（但需要双重记忆！）：
input：
var arr = [1,2,3,4,5] let k = 1 (num steps to rotate) let n = arr.count ( a little but faster )
旋转左 ：
var temp = arr for i in 0..<n { arr[(n-i+k)%n] = temp[i] } result: [2, 1, 4, 3, 5]
旋转右 ：
var temp = arr for i in 0..<n { arr[(i+k)%n] = temp[i] } result: [4, 1, 2, 3, 5]
