Shift elements in array by index
You can use ranged subscripting and concatenate the results. This will give you what you're looking for, with names similar to the standard library:
extension Array {
func shiftRight(var amount: Int = 1) -> [Element] {
guard count > 0 else { return self }
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]
Instead of subscripting, you could also return Array(suffix(count - amount) + prefix(amount)) from shiftRight().
With Swift 5, you can create shift(withDistance:) and shiftInPlace(withDistance:) methods in an Array extension with the following implementation in order to solve your problem:
extension Array {
/**
Returns a new array with the first elements up to specified distance being shifted to the end of the collection. If the distance is negative, returns a new array with the last elements up to the specified absolute distance being shifted to the beginning of the collection.
If the absolute distance exceeds the number of elements in the array, the elements are not shifted.
*/
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])
}
/**
Shifts the first elements up to specified distance to the end of the array. If the distance is negative, shifts the last elements up to the specified absolute distance to the beginning of the array.
If the absolute distance exceeds the number of elements in the array, the elements are not shifted.
*/
mutating func shiftInPlace(withDistance distance: Int = 1) {
self = shift(withDistance: distance)
}
}
Usage:
let array = Array(1...10)
let newArray = array.shift(withDistance: 3)
print(newArray) // prints: [4, 5, 6, 7, 8, 9, 10, 1, 2, 3]
var array = Array(1...10)
array.shiftInPlace(withDistance: -2)
print(array) // prints: [9, 10, 1, 2, 3, 4, 5, 6, 7, 8]
let array = Array(1...10)
let newArray = array.shift(withDistance: 30)
print(newArray) // prints: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
let array = Array(1...10)
let newArray = array.shift(withDistance: 0)
print(newArray) // prints: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
var array = Array(1...10)
array.shiftInPlace()
print(array) // prints: [2, 3, 4, 5, 6, 7, 8, 9, 10, 1]
var array = [Int]()
array.shiftInPlace(withDistance: -2)
print(array) // prints: []
I took a stab at writing some extensions for this. It has some nice features:
- Shifting by an amount greater than
countcauses a wrap-around. - Shifting by negative amounts flips the direction
- Exposes functions as the bit-shift binary operators (
<<,<<=,>>,>>=)
extension Array {
public 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])
}
public func shiftedRight(by rawOffset: Int = 1) -> Array {
return self.shiftedLeft(by: -rawOffset)
}
public mutating func shiftLeftInPlace(by rawOffset: Int = 1) {
if rawOffset == 0 { return /* no-op */ }
func shiftedIndex(for index: Int) -> Int {
let candidateIndex = (index + rawOffset) % self.count
if candidateIndex < 0 {
return candidateIndex + self.count
}
return candidateIndex
}
// Create a sequence of indexs of items that need to be swapped.
//
// For example, to shift ["A", "B", "C", "D", "E"] left by 1:
// Swapping 2 with 0: ["C", "B", "A", "D", "E"]
// Swapping 4 with 2: ["C", "B", "E", "D", "A"]
// Swapping 1 with 4: ["C", "A", "E", "D", "B"]
// Swapping 3 with 1: ["C", "D", "E", "A", "B"] <- Final Result
//
// The sequence here is [0, 2, 4, 1, 3].
// It's turned into [(2, 0), (4, 2), (1, 4), (3, 1)] by the zip/dropFirst trick below.
let indexes = sequence(first: 0, next: { index in
let nextIndex = shiftedIndex(for: index)
if nextIndex == 0 { return nil } // We've come full-circle
return nextIndex
})
print(self)
for (source, dest) in zip(indexes.dropFirst(), indexes) {
self.swapAt(source, dest)
print("Swapping \(source) with \(dest): \(self)")
}
print(Array<(Int, Int)>(zip(indexes.dropFirst(), indexes)))
}
public mutating func shiftRightInPlace(by rawOffset: Int = 1) {
self.shiftLeftInPlace(by: rawOffset)
}
}
public func << <T>(array: [T], offset: Int) -> [T] { return array.shiftedLeft(by: offset) }
public func >> <T>(array: [T], offset: Int) -> [T] { return array.shiftedRight(by: offset) }
public func <<= <T>(array: inout [T], offset: Int) { return array.shiftLeftInPlace(by: offset) }
public func >>= <T>(array: inout [T], offset: Int) { return array.shiftRightInPlace(by: offset) }
You can see it in action here.
Here is a more general solution, which implements this functionality lazily for any type that meets the requirements:
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) }
}
Here's a functional implementation for "in place" rotation that doesn't require extra memory nor a temporary variable and performs no more than one swap per element.
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+s.r)%count // j: index of value for position i
swap(&self[j],&self[s.i]) // swap to place value at rotated index
return (j,s.r) // continue with next index to place
}
}
}
It optimally supports zero, positive and negative rotations as well as rotations of larger magnitude than the array size and rotation of an empty array (i.e. it cannot fail).
Uses negative values to rotate in the other direction (to the right).
Rotating a 3 element array by 10 is like rotating it by 1, the fist nine rotations will bring it back to its initial state (but we don't want to move elements more than once).
Rotating a 5 element array to the right by 3, i.e. rotateLeft(by:-3) is equivalent to rotateLeft(by:2). The function's "effective offset" takes that into account.
An easy solution,
public func solution(_ A : [Int], _ K : Int) -> [Int] {
if A.count > 0 {
let roundedK: Int = K % A.count
let rotatedArray = Array(A.dropFirst(A.count - roundedK) + A.dropLast(roundedK))
return rotatedArray
}
return []
}