在Swift中旋转数组

Question

在Swift中探索算法时,如果不使用funcs shiftLeft/ ,则无法在swift中找到用于数组旋转的算法shiftRight.

C有这个优雅的算法,时间复杂度为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--;
    }
}

我正在努力将其转换为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
    }
} 

据我所知,对于swift,我们需要指定返回类型.如何在不增加空间(内存)复杂性的情况下配置它们？(也就是说,没有创建新的临时数组)

---

这个问题与其他问题不同,因为它关于如何returns在快速工作中与C相比.

Answer 1

我们可以使用切片

func rotLeft(a: [Int], d: Int) -> [Int] {
    let slice1 = a[..<d]
    let slice2 = a[d...]
    return Array(slice2) + Array(slice1)
}

print(rotLeft(a:[1, 2, 3, 4, 5], d: 4))

//prints [5, 1, 2, 3, 4]

Answer 2

你可以扩展Array,你需要让你的方法变异.BTW无需使用临时对象,可以使用Swift swap方法.另一个认为你应该确保参数中传递的索引在数组的有效范围内,为方法添加一个guard语句.试试这样:

extension Array {
    mutating func rotate(positions: Int, size: Int? = nil) {
        guard positions < count && (size ?? 0) <= count else {
            print("invalid input1")
            return
        }
        reversed(start: 0, end: positions - 1)
        reversed(start: positions, end: (size ?? count) - 1)
        reversed(start: 0, end: (size ?? count) - 1)
    }
    mutating func reversed(start: Int, end: Int) {
        guard start >= 0 && end < count && start < end else {
            return
        }
        var start = start
        var end = end
        while start < end, start != end {
            swap(&self[start], &self[end])
            start += 1
            end -= 1
        }
    }
}

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]

Answer 3

当我们在Swift标准库中已有反向函数时，为什么还要创建它呢？我的解决方案（源自Leo Dabus'）：

extension Array {
    mutating func rotate(positions: Int, size: Int? = nil) {
        let size = size ?? count
        guard positions < count && size <= count else { return }

        self[0..<positions].reverse()
        self[positions..<size].reverse()
        self[0..<size].reverse()
    }
}