[Go] Array and string - Rotate Array

Given an array, rotate the array to the right by k steps, where k is non-negative.

 

Example 1:

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

Example 2:

Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Explanation: 
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]

 

Constraints:

• 1 <= nums.length <= 105
• -231 <= nums[i] <= 231 - 1
• 0 <= k <= 105

 

Follow up:

• Try to come up with as many solutions as you can. There are at least three different ways to solve this problem.
• Could you do it in-place with O(1) extra space?

My code

func rotate(nums []int, k int) {
	length := len(nums)
	temp := make([]int, 0)
	if length-k >= 1 {
		temp = append(temp, nums[length-k:]...)
		temp = append(temp, nums[:length-k]...)
		copy(nums, temp)
		return
	} else {
		count := 0
		buf := 0
		for count < k {
			buf = nums[length-1]
			for i := length - 1; i > 0; i-- {
				nums[i] = nums[i-1]
			}
			nums[0] = buf
			count++
		}
		return
	}
}

• First I implimented else part first as example showed.
• But it took a lot of time to run all codes(almost 2k ms).
• So I implimented if part to reduce runtime.
• But it didn't run when k is greater than length.
• As a result, I combined two for it.
• Only append doesn't hand changed array, so copy is needed.

sample 16 ms submission

func Switch(arr []int, l int, r int) {
    for l < r {
        arr[l], arr[r] = arr[r], arr[l]
        l++
        r--
    }
}

func rotate(nums []int, k int)  {
    if len(nums) < 2 {
        return
    }
    if k >= len(nums) {
        k = k%len(nums)
    }

    Switch(nums, 0, len(nums)-1)
    Switch(nums, 0, k-1)
    Switch(nums, k, len(nums)-1)
}

sample 19 ms submission

func rotate(nums []int, k int) {
	if k == 0 || k == len(nums) {
		return
	}
	if k > len(nums) {
		k %= len(nums)
	}
	reverse(nums[0 : len(nums)-k])
	reverse(nums[len(nums)-k:])
	reverse(nums)
}

func reverse(s []int) {
	if len(s) == 0 {
		return
	}
	end := len(s) - 1
	mid := len(s) / 2
	for i := 0; i < mid; i++ {
		s[i], s[end-i] = s[end-i], s[i]
	}
}

sample 20 ms submission

func rotate(nums []int, k int) {
	len := len(nums)

    if 2 > len { // С такими массивами делать ничего не надо
        return
    }

    if k >= len { // k может быть больше чем длинна массива
        k = k % len
    }

    swap(nums, 0, len-1)
    swap(nums, 0, k-1)
    swap(nums, k, len-1)	
}


func swap(arr []int, ldx int, rdx int) {
    for ldx < rdx {
        arr[ldx], arr[rdx] = arr[rdx], arr[ldx]
        ldx++
        rdx--
    }
}

sample 22 ms submission

func rotate(nums []int, k int) {
    n := len(nums)
    k %= n
    reverse(nums, 0, n - 1)
    reverse(nums, 0, k - 1)
    reverse(nums, k, n - 1)
}

func reverse(nums []int, start int, end int) {
    for start < end {
        nums[start], nums[end] = nums[end], nums[start]
        start++
        end--
    }
}

• I think this code is standard.
• first reverse every number.
• second reverse code reverse where surpased number.
• Third reverse code restore original number order.

sample 24 ms submission

func rotate(nums []int, k int)  {
    k=k%len(nums)
    if k!=0{
        copy(nums,append(nums[len(nums)-k:],nums[:len(nums)-k]...))
    }
}

• So simple code it is.
• k will have remainder of k/len(nums).
• when it is 0, array will be same location so codes return as it is.
• this will give minimum roation numbers.

sample 25 ms submission

func rotate(nums []int, k int)  {
    n := len(nums)
    k %= n
    if k == 0 || n == 1 {
        return
    }
    ret := append(nums[n-k:], nums[:n-k]...)
    copy(nums, ret)
}

sample 26 ms submission

func rotate(nums []int, k int)  {
    if nums == nil || len(nums) == 1 {
        return
    }
    k %= len(nums)
    reverse(nums, 0, len(nums)-1)
    reverse(nums, 0, k-1)
    reverse(nums, k, len(nums)-1)
}

func reverse(nums []int, start, end int) {
    for start < end {
        nums[start], nums[end] = nums[end], nums[start]
        start++
        end--
    }
}

sample 27 ms submission

func rotate(nums []int, k int)  {
    length := len(nums);
    rotation := k % length;
    
    cut := length - rotation;
    
    left, right := nums[cut:], nums[:cut];
    
    newArr := append(left, right...);
    
    copy(nums, newArr);
    
}

sample 28 ms submission

func rotate(nums []int, k int) {
    l := len(nums)
    twonums := append(nums, nums...)
    shift := k % l
    
    r := twonums[l-shift:2*l-shift]
    for i := 0; i < len(r); i++ {
        nums[i] = r[i]
    }
}

sample 7500 KB submission

func rotate(nums []int, k int) {
    l := len(nums)
    k = k % l
    for i := 0; i < k; i++ {
        last := nums[l - 1]
        for j := l - 1; j > 0; j-- {
            nums[j] = nums[j - 1]
        }
        nums[0] = last
    }
}

sample 7600 KB submission

func rotate(nums []int, k int)  {
    k = k % len(nums)
    for i := 0; i < k; i++ {
        var val int = nums[len(nums)-1]
        for j := len(nums)-1; j > 0; j-- {
            nums[j] = nums[j-1]
        }
        nums[0] = val
    }
}

sample 7700 KB submission

func rotate(nums []int, k int)  {
    n := len(nums)
    if k == n {
        return
    } else if k > n {
        k = k%n   
    }
    for i:=0; i<k; i++ {
        rotateByOne(nums)
    }
}

func rotateByOne(nums []int) {
    n := len(nums)
    temp := nums[n-1]
    for i:=n-2; i>=0; i-- {
        nums[i+1] = nums[i]
    }
    nums[0] = temp
}

sample 7800 KB submission

func rotate(nums []int, k int)  {
    if len(nums) == 0 {
        return
    }
    k = k % len(nums)
    for ; k > 0; k-- {
        init := nums[len(nums)-1]
        for i := len(nums) -1; i > 0; i -- {
            nums[i] = nums[i-1]
        }
        nums[0] = init
    }
    
}

sample 7900 KB submission

func rotate(nums []int, k int)  {
    if k > len(nums) {
        k = k % len(nums)
    }
    reverse(nums)
    reverse(nums[:k])
    reverse(nums[k:])
}

func reverse(nums []int) {
    i, j := 0, len(nums) - 1
    for i < j {
        nums[i], nums[j] = nums[j], nums[i]
        i++
        j--
    }
}

sample 8000 KB submission

func reverse(nums []int, left, right int) {
	for left < right {
		nums[left], nums[right] = nums[right], nums[left]
		left++
		right--
	}
}

func rotate(nums []int, k int) {
    rot := k % len(nums)
	reverse(nums, 0, len(nums)-1)
	reverse(nums, 0, rot-1)
	reverse(nums, rot, len(nums)-1)
}

sample 8100 KB submission

func rotate(nums []int, k int) {
	c := make([]int, len(nums))
	for k > 0 {
		for i := 0; i < len(nums)-1; i++ {
			c[i+1] = nums[i]
		}
		c[0] = nums[len(nums)-1]
		copy(nums, c)
		k--
	}
}

sample 8200 KB submission

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

func abs(x int) int {
    if x < 0 {
        return -x
    } else {
        return x
    }
}