[leetcode in golang]189、旋转数组

暴力算法

对k个元素进行旋转，从后段提取元素到数组前段

func rotate(nums []int, k int)  {
    pre,temp:=0,0
    for i:=0;i<k;i++{
        pre=nums[len(nums)-1]
        for j:=0;j<len(nums);j++{
            temp=nums[j]
            nums[j]=pre
            pre=temp

        }
    }
}

执行用时308ms，内存消耗7.5M
时间复杂度O(N*K),N个元素移动K次
空间复杂度O(1)

使用另一个数组（额外的空间）

用一个额外的数组来将每个元素放到正确的位置上，也就是原本数组里下标为 ii 的我们把它放到(i+k)%数组长度(这是什么神奇的数学知识)的位置。然后把新的数组拷贝到原数组中。

func rotate(nums []int, k int)  {
   newNums:= make([]int, len(nums))
    for i := 0; i < len(nums); i++{
            newNums[(i + k) % len(nums)] = nums[i]
        }
    for i := 0; i < len(nums); i++{
            nums[i] = newNums[i]
        }
}

执行用时104ms，内存消耗7.7M
时间复杂度O(N)，N个元素遍历一遍
空间复杂度O(N)，新数组长度为原数组长度

环状替换：

func rotate(nums []int, k int)  {
    k=k%len(nums)
    count:=0
    for i:=0;count<len(nums);i++{
        cur:=i
        prev:=nums[i]
        for{
            next:=(cur+k)%len(nums)
            temp:=nums[next]
            nums[next]=prev
            prev=temp
            cur=next
            count++
            if i==cur{
                break
            }
        }
    }
}

执行用时120ms，内存消耗8.1M
时间复杂度O(N)，N个元素遍历一遍
空间复杂度O(1)

环状替换的理解，由于题目k必须存在，在k%len(nums)==0的情况下，数组元素调整后，排序依旧不变。
因此可以将原数组第一个数看作必须要移动的数。
变量temp复制原数组第一个数，将下标为(current + k) % len(nums)的元素与temp调换，最终经过一轮运算(count次)，数组完成重新排序。

_________________leetcode题解中有理解视频。____________________

*current是为了能够遍历整个数组

如果我们直接把每一个数字放到它最后的位置，但这样的后果是遗失原来的元素。因此，我们需要把被替换的数字保存在变量 temp 里面。然后，我们将被替换数字（temp）放到它正确的位置，并继续这个过程 n 次， n 是数组的长度。这是因为我们需要将数组里所有的元素都移动。但是，这种方法可能会有个问题，如果 n%k==0，其中 k=k%n （因为如果 k 大于 n ，移动 k 次实际上相当于移动 k%n次）。这种情况下，我们会发现在没有遍历所有数字的情况下回到出发数字。此时，我们应该从下一个数字开始再重复相同的过程。

slice切片（利用了性质）

自定义方法reverse后调用

有疑问加站长微信联系（非本文作者）