Go: sort.Slice using foreign slice to sort

user_15905673 0
Viewed 120

I'm coding on 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
}

this is one of the answer. But this resolution involves redundant computation of distance, so i want to create a slice to restore the distance. and i'm trying to sort slice points using this foreign data like

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
}

But in this case only slice dist is sorted while the slice points doesn't change. I'm trying to refer to the source code but they seem to be wrapped.

Thanks if anyone could explain it to me or tell me where i can find the answer.

go slice sorting
1 Answers

The purpose and responsibility of less() function you pass to sort.Slice() is to tell the is-less relation of 2 elements of the sortable slice. It should not perform changes on the slice, and it should be idempotent. Your less function is not idempotent: if you call it twice with the same i and j, it may return different result even if the slice is not modified between the calls.

Genesis: your original solution

Your original, improved solution is this:

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]
}

Using an indices slice

One way of sorting a slice based on another is to create a slice holding the indices, sort this indices slice (based on the reference slice), and once we have the final index order, assemble the result.

Here's how it could look like:

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
}

Creating sortable pairs

Another approach is to create pairs from the points and their distances, and sort the pairs.

Here's how it could be done:

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
}

Implementing sort.Interface and using a swap() method that swaps in both slices

Title says it all. We implement sort.Interface ourselves whose less() method will report based on the distance slice, but the swap() function will perform swapping on both slices:

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]
}

Testing the solutions

Here's a test code for all the above solutions:

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)))
}

Which will output (try it on the 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]]
user_17055980
Related