对稀疏 CSC 矩阵 Golang 的行进行排序

Question

我正在尝试分析稀疏矩阵。面临按原始矩阵中元素的升序对行进行排序的任务。但我不明白如何在不损坏空元素的情况下做到这一点。我试图将 sum 数组的元素绑定到行并以某种方式移动它们。但一些元素已从 CSC 结构中删除。可能需要自己更改 li/lj 数组，但我对此没有足够的数学知识。更准确地说，我不明白如何跟踪何时应该重新排列元素，除非在结构中明确指定了额外的元素（零）。package mainimport (    "fmt")type CSC struct {    a, lj, li []int}func getEl(i, j int, el *CSC) int {    for k := el.lj[j]; k < el.lj[j+1]; k++ {        if el.li[k] == i {            return el.a[k]        }    }    return 0}func maxSliceEl(lj []int) int {    max := 0    for _, v := range lj {        if v > max {            max = v        }    }    return max}func main() {    ma := CSC{        a:  []int{8, 2, 5, 7, 1, 9, 2},        li: []int{0, 0, 1, 4, 4, 6, 4},        lj: []int{0, 1, 1, 4, 6, 7},    }    n := len(ma.lj) + 1    m := maxSliceEl(ma.li) - 1    fmt.Printf("Col: %v, Row: %v\n", n, m)    maxStr := []int{}    fmt.Println("Initial matrix:")    for i := 0; i < n; i++ {        sumStrEl := 0        for j := 0; j < m; j++ {            fmt.Print(getEl(i, j, &ma), " ")            sumStrEl += getEl(i, j, &ma)        }        maxStr = append(maxStr, sumStrEl)        fmt.Println("|sumStrEl: ", sumStrEl)    }}

Answer 1

我通过将结构作为解决方案找到了解决问题的方法：元素之和+它们的索引。解决方案比想象中的要简单，只是缺乏解决稀疏矩阵的实践。sum 的位置 [i] 必须作为第一个参数传递给 getEl 函数。

package main

import (

    "fmt"

    "sort"

)

// Creating a CSC (CCS) matrix structure

type CSC struct {

    // Array of values, column indexes, row indexing

    a, lj, li []int

}

// Getting access to the element

func getEl(i, j int, el *CSC) int {

    for k := el.lj[j]; k < el.lj[j+1]; k++ {

        // If the element string is equal to the string of the searched element, then the element is found

        if el.li[k] == i {

            return el.a[k]

        }

    }

    // Otherwise, we will return 0. It will be entered into the matrix

    return 0

}

func maxSliceEl(lj []int) int {

    max := 0

    for _, v := range lj {

        if v > max {

            max = v

        }

    }

    return max

}

type strInfo struct {

    summa int

    pos   int

}

func main() {

    // Set the CSC matrix

    ma := CSC{

        a:  []int{8, 2, 5, 7, 1, 9, 2},

        li: []int{0, 0, 1, 4, 4, 6, 4},

        lj: []int{0, 1, 1, 4, 6, 7},

    }

    // Define the number of columns

    n := len(ma.lj) + 1

    // Define the number of rows

    m := maxSliceEl(ma.li) - 1

    fmt.Printf("Cols: %v, Rows: %v\n", m, n)

    // Set a variable with a structure type for calculating 

    // the amount in a row and indexing each element in it

    var stringsInfo []strInfo

    fmt.Println("Initial matrix:")

    for i := 0; i < n; i++ {

        sumStrEl := 0

        for j := 0; j < m; j++ {

            sumStrEl += getEl(i, j, &ma)

            fmt.Print(getEl(i, j, &ma), " ")

        }

        fmt.Println("|", sumStrEl)

        // Adding a cell with the sum and index to the slice

        var strI strInfo

        strI.summa = sumStrEl

        strI.pos = i

        stringsInfo = append(stringsInfo, strI)

    }

    fmt.Println("stringsInfo: ", stringsInfo)

    // Sorting the stringsInfo slice in ascending order of the sum elements

    sort.Slice(stringsInfo, func(i, j int) (less bool) {

        return stringsInfo[i].summa < stringsInfo[j].summa

    })

    fmt.Println("stringsInfo: ", stringsInfo)

    fmt.Println("Sorted matrix:")

    for i := range stringsInfo {

        for j := 0; j < m; j++ {

            // Output the matrix by idnex stringsInfo[i].pos

            fmt.Print(getEl(stringsInfo[i].pos, j, &ma), " ")

        }

        fmt.Println("|", stringsInfo[i].summa)

    }

}