I want to know if there's a good way to return true if both integers can be merged but it must be in consecutive means, {100,101} can be merge with {103, 104, 102 }, but not {100,101} and {103,104,105} (Missing 102) coding based on the question.
package main
import (
"fmt"
"math/rand"
"time"
)
func main() {
slice := generateSlice(20)
fmt.Println("
--- Unsorted ---
", slice)
fmt.Println("
--- Sorted ---
", mergeSort(slice), "
")
}
// Generates a slice of size, size filled with random numbers
func generateSlice(size int) []int {
slice := make([]int, size, size)
rand.Seed(time.Now().UnixNano())
for i := 0; i < size; i++ {
slice[i] = rand.Intn(999) - rand.Intn(999)
}
return slice
}
func mergeSort(items []int) []int {
var num = len(items)
if num == 1 {
return items
}
middle := int(num / 2)
var (
left = make([]int, middle)
right = make([]int, num-middle)
)
for i := 0; i < num; i++ {
if i < middle {
left[i] = items[i]
} else {
right[i-middle] = items[i]
}
}
return merge(mergeSort(left), mergeSort(right))
}
func merge(left, right []int) (result []int) {
result = make([]int, len(left) + len(right))
i := 0
for len(left) > 0 && len(right) > 0 {
if left[0] < right[0] {
result[i] = left[0]
left = left[1:]
} else {
result[i] = right[0]
right = right[1:]
}
i++
}
for j := 0; j < len(left); j++ {
result[i] = left[j]
i++
}
for j := 0; j < len(right); j++ {
result[i] = right[j]
i++
}
return
}
Output:
https://play.golang.org/p/oAtGTiUnxrE
The question:
A pumpung is a permutation of consecutive integers, possibly with repeated items. Two pumpungs can be merged if they form a bigger pumpung. For example, [100, 101] and [103, 102, 104], [222, 221, 220, 219] and [221, 222, 223, 225, 224] can be merged; whereas [100, 101] and [103, 104, 105] cannot. Write a function, IsMergeable(pumpung1, pumpung2), returning true iff the given pumpungs can be merged. You may assume that the arguments are really pumpungs.
</div>
For example,
package main
import "fmt"
const (
maxInt = int(^uint(0) >> 1)
minInt = -maxInt - 1
)
func isMerge(a1, a2 []int) bool {
min1, max1 := maxInt, minInt
for _, e1 := range a1 {
if min1 > e1 {
min1 = e1
}
if max1 < e1 {
max1 = e1
}
}
for _, e2 := range a2 {
if e2 == min1-1 || e2 == max1+1 {
return true
}
}
return false
}
func main() {
a1 := []int{100, 101}
a2 := []int{103, 104, 102}
a3 := []int{103, 104, 105}
fmt.Println(a1, a2, isMerge(a1, a2))
fmt.Println(a2, a1, isMerge(a2, a1))
fmt.Println(a1, a3, isMerge(a1, a3))
fmt.Println(a3, a1, isMerge(a3, a1))
a4 := []int{222, 221, 220, 219}
a5 := []int{221, 222, 223, 225, 224}
fmt.Println(a4, a5, isMerge(a4, a5))
fmt.Println(a5, a4, isMerge(a5, a4))
}
Playground: https://play.golang.org/p/rRGPoivhEWW
Output:
[100 101] [103 104 102] true
[103 104 102] [100 101] true
[100 101] [103 104 105] false
[103 104 105] [100 101] false
[222 221 220 219] [221 222 223 225 224] true
[221 222 223 225 224] [222 221 220 219] true