问题描述
在Swift中探索算法时,如果不使用funcs shiftLeft
/ shiftRight 。
While exploring algorithms in Swift, couldn't find algorithm for array rotation in swift without using funcs
shiftLeft
/ shiftRight
.
C具有这种优美的算法,其时间复杂度为O(N):
C has this graceful algo with time complexity of O(N):
/* Function to left rotate arr[] of size n by d */
void leftRotate(int arr[], int d, int n)
{
rvereseArray(arr, 0, d-1);
rvereseArray(arr, d, n-1);
rvereseArray(arr, 0, n-1);
}
/*Function to reverse arr[] from index start to end*/
void rvereseArray(int arr[], int start, int end)
{
int temp;
while (start < end)
{
temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
}
我正在努力将其转换为快速的:
I'm struggling with converting this into swift:
func rotate(array:[Int], positions:Int, arSize:Int) {
var a = array
var p = positions
var s = arSize
reverseArray(array: a, start: 0, end: p-1)
reverseArray(array: a, start: p, end: s-1)
reverseArray(array: a, start: 0, end: s-1)
}
func reverseArray(array: [Int], start:Int, end:Int) {
var a = array
var s = start
var e = end
var temp = 0
while s < e {
temp = a[s]
a[s] = a[e]
a[e] = temp
s += 1
e -= 1
}
}
据我所知,为了迅速,我们需要指定返回类型。
如何在不增加空间(内存)复杂性的情况下进行配置? (又名,而不创建新的临时数组)
As I understand, for swift, we need to specify return types.How they should be configured without increasing space(memory) complexity? (aka, without creating new temporary arrays)
此问题与其他问题有所不同,因为它关于<$ c $
This question is different from others, because its about how
returns
work in swift compare to C.
推荐答案
编辑更新:
Swift 5或更高版本
extension RangeReplaceableCollection {
mutating func rotate(positions: Int) {
let index = self.index(startIndex, offsetBy: positions, limitedBy: endIndex) ?? endIndex
let slice = self[..<index]
removeSubrange(..<index)
insert(contentsOf: slice, at: endIndex)
}
}
extension RangeReplaceableCollection where Self: BidirectionalCollection {
mutating func rotate(positions: Int, size: Int) {
let index = self.index(startIndex, offsetBy: positions, limitedBy: endIndex) ?? endIndex
let end = self.index(index, offsetBy: size - positions, limitedBy: self.index(before: endIndex)) ?? endIndex
replaceSubrange(..<index, with: self[..<index].reversed())
replaceSubrange(index..<end, with: self[index..<end].reversed())
replaceSubrange(..<end, with: self[..<end].reversed())
}
}
var test = [1,2,3,4,5,6,7,8,9,10]
test.rotate(positions: 3) // [4, 5, 6, 7, 8, 9, 10, 1, 2, 3]
var test2 = "1234567890"
test2.rotate(positions: 3) // "4567890123"
这篇关于在Swift中旋转数组的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!