Golang-数组

1. 拷贝

1.1 append

package main

import "fmt"

func main() {
    src := []int{1, 2, 3}
    fmt.Println("source slice:", src)

    // Using append
    dst := append([]int(nil), src...)
    fmt.Println("destination slice (using append):", dst)
}

1.2 copy

package main

import "fmt"

func main() {
    src := []int{1, 2, 3}
    fmt.Println("source slice:", src)

    // Copying all elements
    dst1 := make([]int, len(src))
    n := copy(dst1, src)
    fmt.Println("destination slice (all elements):", dst1)
    fmt.Println("number of elements copied:", n)

    // Copying only first two elements
    dst2 := make([]int, 2)
    n = copy(dst2, src)
    fmt.Println("destination slice (first two elements):", dst2)
    fmt.Println("number of elements copied:", n)
}

1.3 append vs. copy

通过append和copy进行拷贝数组都是深拷贝，通过=拷贝是引用，浅拷贝。一般来讲appeend更常用一点，但是copy()可以通过cap指定拷贝元素数量。

1.4 s[low:high:max]

通过这种语法可以进行构造数组，数组的元素是s[low:high]，cap是max-low。

package main

import (
	"fmt"
)

func main() {
	s := []int{1, 2, 3, 4}
	a := s[1:3:4]
	fmt.Println(cap(a))  // 3
	fmt.Println(s) // [2 3]
}

1.4 append的容量

通过append进行拷贝，如果slice本身容量足够，就在slice末尾添加元素；如果容量不够，就会进行扩容，容量变成原来的2倍。

package main

import "fmt"

func main() {
	slice := []int{1}
	fmt.Println(cap(slice)) // 1
	slice = append(slice, 2) 
	fmt.Println(cap(slice)) // 2
	slice = append(slice, 3) 
	fmt.Println(cap(slice)) // 4
	x := append(slice, 4)
	fmt.Println(cap(slice)) // 4
	y := append(slice, 5)
	fmt.Println(cap(slice)) //4

	// [1 2 3] [1 2 3 5] [1 2 3 5]
	fmt.Println(slice, x, y)

}

2.插入

2.1 在末尾插入

package main

import "fmt"

func main() {
    s := []int{1, 2, 3}
    fmt.Println(s) // [1 2 3]

    // Insert 4 at tail
    s = append(s, 4)
    fmt.Println(s) // [1 2 3 4]
}

2.2 在中间插入

package main

import "fmt"

func main() {
    s := []int{1, 2, 3}
    fmt.Println(s) // [1 2 3]

    // Insert 4 at index 1
    index := 1
    s = append(s[:index], append([]int{4}, s[index:]...)...)
    fmt.Println(s) // [1 4 2 3]
}

1.3 自定义排序

type Person struct {
    Name string
    Age  int
}

type ByAge []Person

func (a ByAge) Len() int           { return len(a) }
func (a ByAge) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
func (a ByAge) Less(i, j int) bool { return a[i].Age < a[j].Age }

func main() {
    people := []Person{
        {"Bob", 31},
        {"John", 42},
        {"Michael", 17},
        {"Jenny", 26},
    }

	// [{Bob 31} {John 42} {Michael 17} {Jenny 26}]
    fmt.Println(people)
    sort.Sort(ByAge(people))
    // [{Michael 17} {Jenny 26} {Bob 31} {John 42}]
    fmt.Println(people)
}

package main

import (
	"fmt"
	"sort"
)

// 为了在 Go 中使用自定义函数进行排序，我们需要一个对应的类型。
// 我们在这里创建了一个 `byLength` 类型，它只是内建类型 `[]string` 的别名。
type byLength []string

// 我们为该类型实现了 `sort.Interface` 接口的 `Len`、`Less` 和 `Swap` 方法，
// 这样我们就可以使用 `sort` 包的通用 `Sort` 方法了，
// `Len` 和 `Swap` 在各个类型中的实现都差不多，
// `Less` 将控制实际的自定义排序逻辑。
// 在这个的例子中，我们想按字符串长度递增的顺序来排序，
// 所以这里使用了 `len(s[i])` 和 `len(s[j])` 来实现 `Less`。
func (s byLength) Len() int { return len(s) }
func (s byLength) Swap(i, j int) { s[i], s[j] = s[j], s[i] }
func (s byLength) Less(i, j int) bool { return len(s[i]) < len(s[j]) }

// 一切准备就绪后，我们就可以通过将切片 `fruits` 强转为 `byLength` 类型的切片，
// 然后对该切片使用 `sort.Sort` 来实现自定义排序。
func main() {
	fruits := []string{"peach", "banana", "kiwi"}
	sort.Sort(byLength(fruits))
	fmt.Println(fruits)
}

1.4 大根堆/小根堆

1.4.1 接口实现

因为go中没有现成的堆可以用，只提供了heap的接口，所以需要自己实现相应的接口。

需要实现这些接口：

type Interface interface {
    sort.Interface
    Push(x interface{}) // add x as element Len()
    Pop() interface{}   // remove and return element Len() - 1.
}

接口实现如下：

type IntHeap struct {
	heap []int
	// 是否小根堆
	isMin bool
}

func (h IntHeap) Len() int { return len(h.heap) }

func (h IntHeap) Swap(i, j int) { h.heap[i], h.heap[j] = h.heap[j], h.heap[i] }

func (h IntHeap) Less(i, j int) bool {
	if h.isMin {
		return h.heap[i] < h.heap[j]
	}
	return h.heap[i] > h.heap[j]
}

func (h *IntHeap) Push(x interface{}) { h.heap = append(h.heap, x.(int)) }

func (h *IntHeap) Pop() interface{} {
	x := h.heap[h.Len()-1]
	h.heap = h.heap[0 : h.Len()-1]
	return x
}

调用示例：

func main() {
	minHeap := IntHeap{
		heap:  []int{2, 1, 5},
		isMin: true,
	}
	heap.Init(&minHeap)
	heap.Push(&minHeap, 3)
	fmt.Printf("minimum: %d\n", minHeap.heap[0])
	for minHeap.Len() > 0 {
		fmt.Printf("%d ", heap.Pop(&minHeap))
	}
	fmt.Println()

	maxHeap := IntHeap{
		heap:  []int{2, 1, 5},
		isMin: false,
	}
	heap.Init(&maxHeap)
	heap.Push(&maxHeap, 3)
	fmt.Printf("maximum: %d\n", maxHeap.heap[0])
	for maxHeap.Len() > 0 {
		fmt.Printf("%d ", heap.Pop(&maxHeap))
	}
}

输出结果如下：

minimum: 1
1 2 3 5 
maximum: 5
5 3 2 1 

1.4.2 源码

// Copyright 2009 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// Package heap provides heap operations for any type that implements
// heap.Interface. A heap is a tree with the property that each node is the
// minimum-valued node in its subtree.
//
// The minimum element in the tree is the root, at index 0.
//
// A heap is a common way to implement a priority queue. To build a priority
// queue, implement the Heap interface with the (negative) priority as the
// ordering for the Less method, so Push adds items while Pop removes the
// highest-priority item from the queue. The Examples include such an
// implementation; the file example_pq_test.go has the complete source.
//
package heap

import "sort"

// The Interface type describes the requirements
// for a type using the routines in this package.
// Any type that implements it may be used as a
// min-heap with the following invariants (established after
// Init has been called or if the data is empty or sorted):
//
//	!h.Less(j, i) for 0 <= i < h.Len() and 2*i+1 <= j <= 2*i+2 and j < h.Len()
//
// Note that Push and Pop in this interface are for package heap's
// implementation to call. To add and remove things from the heap,
// use heap.Push and heap.Pop.
type Interface interface {
	sort.Interface
	Push(x any) // add x as element Len()
	Pop() any   // remove and return element Len() - 1.
}

// Init establishes the heap invariants required by the other routines in this package.
// Init is idempotent with respect to the heap invariants
// and may be called whenever the heap invariants may have been invalidated.
// The complexity is O(n) where n = h.Len().
func Init(h Interface) {
	// heapify
	n := h.Len()
	for i := n/2 - 1; i >= 0; i-- {
		down(h, i, n)
	}
}

// Push pushes the element x onto the heap.
// The complexity is O(log n) where n = h.Len().
func Push(h Interface, x any) {
	h.Push(x)
	up(h, h.Len()-1)
}

// Pop removes and returns the minimum element (according to Less) from the heap.
// The complexity is O(log n) where n = h.Len().
// Pop is equivalent to Remove(h, 0).
func Pop(h Interface) any {
	n := h.Len() - 1
	h.Swap(0, n)
	down(h, 0, n)
	return h.Pop()
}

// Remove removes and returns the element at index i from the heap.
// The complexity is O(log n) where n = h.Len().
func Remove(h Interface, i int) any {
	n := h.Len() - 1
	if n != i {
		h.Swap(i, n)
		if !down(h, i, n) {
			up(h, i)
		}
	}
	return h.Pop()
}

// Fix re-establishes the heap ordering after the element at index i has changed its value.
// Changing the value of the element at index i and then calling Fix is equivalent to,
// but less expensive than, calling Remove(h, i) followed by a Push of the new value.
// The complexity is O(log n) where n = h.Len().
func Fix(h Interface, i int) {
	if !down(h, i, h.Len()) {
		up(h, i)
	}
}

func up(h Interface, j int) {
	for {
		i := (j - 1) / 2 // parent
		if i == j || !h.Less(j, i) {
			break
		}
		h.Swap(i, j)
		j = i
	}
}

func down(h Interface, i0, n int) bool {
	i := i0
	for {
		j1 := 2*i + 1
		if j1 >= n || j1 < 0 { // j1 < 0 after int overflow
			break
		}
		j := j1 // left child
		if j2 := j1 + 1; j2 < n && h.Less(j2, j1) {
			j = j2 // = 2*i + 2  // right child
		}
		if !h.Less(j, i) {
			break
		}
		h.Swap(i, j)
		i = j
	}
	return i > i0
}