Go语言中高效管理整数列表：查找、添加与删除操作的策略与实现

// 获取索引为i的元素
value := mySlice[i]

// 在切片末尾添加元素
mySlice = append(mySlice, newValue)

// 删除索引为i的元素
mySlice = append(mySlice[:i], mySlice[i+1:]...)

// 线性查找元素
func linearSearch(slice []int, target int) (int, bool) {
    for i, v := range slice {
        if v == target {
            return i, true // 找到目标，返回索引和true
        }
    }
    return -1, false // 未找到目标
}

package main

import (
    "fmt"
    "sort"
)

// Ints 是一个有序的整数切片
type Ints []int

// Append 将值v插入到有序切片中，保持其排序状态。
// 查找插入位置的时间复杂度为 O(log n)，但实际的切片插入（数据移动）
// 导致整体插入操作的时间复杂度为 O(n)。
func (ints *Ints) Append(v int) {
    // 使用 sort.SearchInts 找到v应该插入的位置，保持切片有序
    // sort.SearchInts 返回第一个大于或等于v的元素的索引
    i := sort.SearchInts(*ints, v)

    // 创建一个包含v的新切片
    newValSlice := []int{v}

    // 将原始切片分为两部分：[0:i] 和 [i:]
    // 然后将 newValslice 插入到两部分之间
    *ints = append((*ints)[:i], append(newValSlice, (*ints)[i:]...)...)
}

// Delete 根据索引i删除元素。
// 时间复杂度为 O(n)，因为需要移动 i+1 之后的元素。
func (ints *Ints) Delete(i int) {
    if i < 0 || i >= len(*ints) {
        return // 索引越界
    }
    *ints = append((*ints)[:i], (*ints)[i+1:]...)
}

// Search 在有序切片中查找值v。
// 利用 sort.SearchInts 进行二分查找，时间复杂度为 O(log n)。
func (ints Ints) Search(v int) (int, bool) {
    // sort.SearchInts 返回第一个大于或等于v的元素的索引
    i := sort.SearchInts(ints, v)
    // 检查找到的索引是否有效且对应的值是否等于v
    if i < len(ints) && ints[i] == v {
        return i, true // 找到目标，返回索引和true
    }
    return -1, false // 未找到目标
}

// Get 根据索引获取元素
func (ints Ints) Get(i int) (int, bool) {
    if i < 0 || i >= len(ints) {
        return 0, false // 索引越界
    }
    return ints[i], true
}

func main() {
    // 初始化一个容量为1000的有序整数切片
    data := make(Ints, 0, 1000)

    // 添加元素
    data.Append(50)
    data.Append(10)
    data.Append(70)
    data.Append(30)
    data.Append(100)
    data.Append(20)
    fmt.Println("添加元素后:", data) // 预期输出: [10 20 30 50 70 100]

    // 查找元素
    index, ok := data.Search(30)
    if ok {
        fmt.Printf("找到 30，索引为: %d\n", index) // 预期输出: 找到 30，索引为: 2
    } else {
        fmt.Println("未找到 30")
    }

    index, ok = data.Search(45)
    if ok {
        fmt.Printf("找到 45，索引为: %d\n", index)
    } else {
        fmt.Println("未找到 45") // 预期输出: 未找到 45
    }

    // 获取元素
    val, ok := data.Get(1)
    if ok {
        fmt.Printf("索引 1 处的元素是: %d\n", val) // 预期输出: 索引 1 处的元素是: 20
    }

    // 删除元素 (删除索引为2的元素，即30)
    data.Delete(2)
    fmt.Println("删除索引2的元素后:", data) // 预期输出: [10 20 50 70 100]

    // 再次查找被删除的元素
    _, ok = data.Search(30)
    if ok {
        fmt.Println("再次找到 30")
    } else {
        fmt.Println("再次查找，未找到 30") // 预期输出: 再次查找，未找到 30
    }
}

package main

import "fmt"

// IntSet 是一个基于map的整数集合
type IntSet map[int]struct{}

// NewIntSet 创建一个新的整数集合
func NewIntSet() IntSet {
    return make(IntSet)
}

// Add 将整数v添加到集合中。
// 平均时间复杂度为 O(1)。
func (s IntSet) Add(v int) {
    s[v] = struct{}{}
}

// Delete 从集合中删除整数v。
// 平均时间复杂度为 O(1)。
func (s IntSet) Delete(v int) {
    delete(s, v)
}

// Contains 检查集合中是否存在整数v。
// 平均时间复杂度为 O(1)。
func (s IntSet) Contains(v int) bool {
    _, found := s[v]
    return found
}

// ToSlice 将集合转换为切片（无序）。
// 时间复杂度为 O(n)。
func (s IntSet) ToSlice() []int {
    slice := make([]int, 0, len(s))
    for k := range s {
        slice = append(slice, k)
    }
    return slice
}

func main() {
    set := NewIntSet()

    // 添加元素
    set.Add(10)
    set.Add(50)
    set.Add(20)
    set.Add(10) // 重复添加不会改变集合内容
    fmt.Println("添加元素后:", set.ToSlice()) // 顺序可能不固定

    // 查找元素
    fmt.Printf("集合中是否包含 20: %t\n", set.Contains(20)) // 预期输出: true
    fmt.Printf("集合中是否包含 30: %t\n", set.Contains(30)) // 预期输出: false

    // 删除元素
    set.Delete(50)
    fmt.Println("删除 50 后:", set.ToSlice()) // 预期输出: 移除 50

    // 再次查找被删除的元素
    fmt.Printf("删除 50 后，集合中是否包含 50: %t\n", set.Contains(50)) // 预期输出: false
}