Leetcode Array101 Duplicate Zeros in GO

손진성·2022년 2월 21일
0

Given a fixed-length integer array arr, duplicate each occurrence of zero, shifting the remaining elements to the right.

Note that elements beyond the length of the original array are not written. Do the above modifications to the input array in place and do not return anything.

Constraints:
1 <= arr.length <= 104
0 <= arr[i] <= 9

My code

func duplicateZeros(arr []int) {
	for x := 0; x < len(arr)-1; x++ {
		if arr[x] == 0 {
			arr = shift(arr, x)
			arr[x+1] = 0
			x++
		}
	}
}

func shift(arr []int, x int) []int {
	for y := len(arr) - 2; y >= x+1; y-- {
		arr[y+1] = arr[y]
	}
	return arr
}

1) First I implimented for loop to check coverage of Loop
2) if array[x] is 0, shift function first and then allocate 0 to x+1
3) not to make duplicate 0, I used x incrementer to skip duplicated zero.
4) for code visibility, I implemented shift func
5) Why y := len(arr)-2?
due to shift maximum with y+1, It should be less than len(arr)-1(x maximum)

sample 0 ms submission

func duplicateZeros(arr []int)  {
    temp := make([]int, len(arr))
    
    ia := 0
    it := 0
    
    for it < len(arr) {
        if arr[ia] != 0 {
            temp[it] = arr[ia]
            it += 1
            ia += 1
        } else {
            it += 2
            ia += 1
        }
    }
    
    for i, num := range temp {
        arr[i] = num
    }
}
  • Used empty array for calculation.
  • Empty array means 0, So this code didn't use to input 0.
  • After completion, arr received values of temp array.
  • Is there any solution to return temp instead arr? then it will be more faster..

After modification

func duplicateZeros(arr []int) {
	temp := make([]int, len(arr))
	t := 0
	a := 0

	for t < len(arr) {
		if arr[a] != 0 {
			temp[t] = arr[a]
			t += 1
			a += 1
		} else {
			t += 2
			a += 1
		}
	}
	copy(arr, temp)
}
  • Copy works like pass by reference.
  • It worked in Leetcode

Sample 2 ms submission & sample 3100 KB submission

func duplicateZeros(arr []int)  {
    for i := 0; i < len(arr) - 1; i++ {
        if arr[i] == 0 {
            copy(arr[i+1:], arr[i:])
            i++
        } 
    }
  • Looks very simple
  • If the length of src is greater than the length of dst, then the number of elements copied is the length of dst
  • If the length of dst is greater than length of src, then number of elements copied is length of src

sample 3100 KB submission

func duplicateZeros(arr []int)  {
  for i := 0; i < len(arr); i++ {
    if arr[i] == 0 {
      for j := len(arr)-1; j > i; j-- {
        arr[j] = arr[j-1]
      }
      arr[i] = 0
      i++
    }
  }  
}

modification

func duplicateZeros(arr []int) {
	for i := 0; i < len(arr); i++ {
		if arr[i] == 0 {
			for j := len(arr) - 1; j > i; j-- {
				arr[j] = arr[j-1]
			}
			i++
		}
	}
}
  • Original code does not modify array having 0, so arr(i) does not need.
profile
Gopyther

0개의 댓글