在Swift中旋转数组

发布时间：2020-12-14 04:49:42 所属栏目：百科来源：网络整理

导读：在 Swift中探索算法时,如果不使用funcs shiftLeft / shiftRight,则无法在swift中找到用于数组旋转的算法. C有这个优雅的算法,时间复杂度为O(N)： /* Function to left rotate arr[] of size n by d */void leftRotate(int arr[],int d,int n){ rvereseArray(

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

C有这个优雅的算法,时间复杂度为O(N)：

/* Function to left rotate arr[] of size n by d */
void leftRotate(int arr[],int d,int n)
{
    rvereseArray(arr,d-1);
    rvereseArray(arr,d,n-1);
    rvereseArray(arr,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,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,我们需要指定返回类型.
如何在不增加空间(内存)复杂性的情况下配置它们？ (也就是说,没有创建新的临时数组)

这个问题与其他问题不同,因为它与C相比,它的回报如何迅速发挥作用.

解决方法

你可以扩展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,10,1,3]

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!