Go：sort.Slice使用自定义切片进行排序

怎么入门Golang编程？需要学习哪些知识点？这是新手们刚接触编程时常见的问题；下面golang学习网就来给大家整理分享一些知识点，希望能够给初学者一些帮助。本篇文章就来介绍《Go：sort.Slice使用自定义切片进行排序》，涉及到，有需要的可以收藏一下

我正在 leetcode 973 上编码。

func kclosest(points [][]int, k int) [][]int {

    sort.slice(points, func(i, j int) bool {
           if hypot(points[i]) > hypot(points[j]){
               return false
           }else{
               return true
           }
        })
    return points[:k]
}

func hypot(point []int) int {
    ans := 0
    for _, n := range point{
        ans+=n*n
    }
    return ans
}

这是答案之一。但这个分辨率涉及到距离的冗余计算，所以我想创建一个切片来恢复距离。我正在尝试使用这些外部数据对切片点进行排序

func kClosest(points [][]int, k int) [][]int {
    dist := make([]int, len(points))
    for i:=0; i< len(points); i++{
        dist[i] = hypot(points[i])
    }

    sort.Slice(points, func(i, j int) bool {
           if dist[i] > dist[j]{
               dist[i], dist[j] = dist[j], dist[i]
               return false
           }else{
               return true
           }
        })
    return points[:k]
}

func hypot(point []int) int {
    ans := 0
    for _, n := range point{
        ans+=n*n
    }
    return ans
}

但在这种情况下，仅对切片距离进行排序，而切片点不会改变。 我试图参考源代码，但它们似乎已被包装。

如果有人可以向我解释或告诉我在哪里可以找到答案，谢谢。

正确答案

传递给 sort.slice() 的 less() 函数的目的和责任是告诉可排序切片的 2 个元素的 is-less 关系。它不应该对切片执行更改，并且应该是幂等的。您的 less 函数不是幂等的：如果您使用相同的 i 和 j 调用它两次，即使在调用之间未修改切片，它也可能返回不同的结果。

genesis：您的原始解决方案

您最初的改进解决方案是这样的：

func kclosest(points [][]int, k int) [][]int {
    sort.slice(points, func(i, j int) bool {
        return hypot(points[i]) < hypot(points[j])
    })
    return points[:k]
}

使用 indices 切片

基于另一个切片对切片进行排序的一种方法是创建一个保存索引的切片，对该索引切片进行排序（基于参考切片），一旦我们获得了最终的索引顺序，就组装结果。

它可能是这样的：

func kclosest2(points [][]int, k int) [][]int {
    dist := make([]int, len(points))
    indices := make([]int, len(points))
    for i := range dist {
        indices[i] = i
        dist[i] = hypot(points[i])
    }

    sort.slice(indices, func(i, j int) bool {
        return dist[indices[i]] <= dist[indices[j]]
    })

    result := make([][]int, k)
    for i := range result {
        result[i] = points[indices[i]]
    }
    return result
}

创建可排序对

另一种方法是根据点及其距离创建对，并对这些对进行排序。

具体实现方法如下：

func kclosest3(points [][]int, k int) [][]int {
    type pair struct {
        dist  int
        point []int
    }

    pairs := make([]pair, len(points))
    for i := range pairs {
        pairs[i].dist = hypot(points[i])
        pairs[i].point = points[i]
    }

    sort.slice(pairs, func(i, j int) bool {
        return pairs[i].dist <= pairs[j].dist
    })

    result := make([][]int, k)
    for i := range result {
        result[i] = pairs[i].point
    }
    return result
}

实现 sort.interface 并使用 swap() 方法在两个切片中进行交换

标题说明了一切。我们自己实现了 sort.Interface，其 less() 方法将根据距离切片进行报告，但 swap() 函数将在两个切片上执行交换：

type mysorter struct {
    dist   []int
    points [][]int
}

func (m mysorter) len() int { return len(m.dist) }
func (m mysorter) swap(i, j int) {
    m.dist[i], m.dist[j] = m.dist[j], m.dist[i]
    m.points[i], m.points[j] = m.points[j], m.points[i]
}
func (m mysorter) less(i, j int) bool { return m.dist[i] < m.dist[j] }

func kclosest4(points [][]int, k int) [][]int {
    dist := make([]int, len(points))
    for i := range dist {
        dist[i] = hypot(points[i])
    }

    ms := mysorter{dist, points}

    sort.sort(ms)
    return points[:k]
}

测试解决方案

这是上述所有解决方案的测试代码：

solutions := []func(points [][]int, k int) [][]int{
    kclosest, kclosest2, kclosest3, kclosest4,
}
for _, solution := range solutions {
    points := [][]int{
        {3, 5},
        {0, 5},
        {0, 0},
        {1, 2},
        {6, 0},
    }
    fmt.println(solution(points, len(points)))
}

将输出（在 Go Playground 上尝试）

[[0 0] [1 2] [0 5] [3 5] [6 0]]
[[0 0] [1 2] [0 5] [3 5] [6 0]]
[[0 0] [1 2] [0 5] [3 5] [6 0]]
[[0 0] [1 2] [0 5] [3 5] [6 0]]

好了，本文到此结束，带大家了解了《Go：sort.Slice使用自定义切片进行排序》，希望本文对你有所帮助！关注golang学习网公众号，给大家分享更多Golang知识！