상세 컨텐츠

본문 제목

Quick sort with merge array in Go

Go/Leet Code

by Gopythor 2022. 2. 24. 00:33

본문

728x90
반응형

It works in VScode and Go playground, but Leetcode gave me different result.
So I will try to make another solution.

package main

import "fmt"

func main() {
    nums1 := []int{1, 2, 3, 0, 0, 0}
    nums2 := []int{2, 5, 6}
    merge(nums1, len(nums1), nums2, len(nums2))
    fmt.Println(nums1) // [1 2 2 3 5 6]
}

func merge(nums1 []int, m int, nums2 []int, n int) {
    count := 0
    temp := append(nums1, nums2...)
    temp = quicksort(temp, 0, m+n-1)
    for i := range temp {
        if temp[i] == 0 {
            count++
        }
    }
    temp = temp[count:]

    for j := range nums1 {
        nums1[j] = temp[j] //self assignment for sure
    }

}
func quicksort(arr []int, low, high int) []int {
    if low < high {
        arr, p := partition(arr, low, high)
        arr = quicksort(arr, low, p-1)
        arr = quicksort(arr, p+1, high)
    }
    return arr
}

func partition(arr []int, low, high int) ([]int, int) {
    pivot := arr[high]
    i := low
    for j := low; j < high; j++ {
        if arr[j] < pivot {
            arr[i], arr[j] = arr[j], arr[i]
            i++
        }
    }
    arr[i], arr[high] = arr[high], arr[i]
    return arr, i
}

https://go.dev/play/p/v3O15UuMs-N

728x90
반응형

관련글 더보기

댓글 영역