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

Question

我正在尝试分析稀疏矩阵。面临按原始矩阵中元素的升序对行进行排序的任务。

但我不明白如何在不损坏空元素的情况下做到这一点。

我试图将 sum 数组的元素绑定到行并以某种方式移动它们。但一些元素已从 CSC 结构中删除。

可能需要自己更改 li/lj 数组，但我对此没有足够的数学知识。更准确地说，我不明白如何跟踪何时应该重新排列元素，除非在结构中明确指定了额外的元素（零）。

package main

import (

    "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 mainimport (&nbsp; &nbsp; "fmt"&nbsp; &nbsp; "sort")// Creating a CSC (CCS) matrix structuretype CSC struct {&nbsp; &nbsp; // Array of values, column indexes, row indexing&nbsp; &nbsp; a, lj, li []int}// Getting access to the elementfunc getEl(i, j int, el *CSC) int {&nbsp; &nbsp; for k := el.lj[j]; k < el.lj[j+1]; k++ {&nbsp; &nbsp; &nbsp; &nbsp; // If the element string is equal to the string of the searched element, then the element is found&nbsp; &nbsp; &nbsp; &nbsp; if el.li[k] == i {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return el.a[k]&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; // Otherwise, we will return 0. It will be entered into the matrix&nbsp; &nbsp; return 0}func maxSliceEl(lj []int) int {&nbsp; &nbsp; max := 0&nbsp; &nbsp; for _, v := range lj {&nbsp; &nbsp; &nbsp; &nbsp; if v > max {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; max = v&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; return max}type strInfo struct {&nbsp; &nbsp; summa int&nbsp; &nbsp; pos&nbsp; &nbsp;int}func main() {&nbsp; &nbsp; // Set the CSC matrix&nbsp; &nbsp; ma := CSC{&nbsp; &nbsp; &nbsp; &nbsp; a:&nbsp; []int{8, 2, 5, 7, 1, 9, 2},&nbsp; &nbsp; &nbsp; &nbsp; li: []int{0, 0, 1, 4, 4, 6, 4},&nbsp; &nbsp; &nbsp; &nbsp; lj: []int{0, 1, 1, 4, 6, 7},&nbsp; &nbsp; }&nbsp; &nbsp; // Define the number of columns&nbsp; &nbsp; n := len(ma.lj) + 1&nbsp; &nbsp; // Define the number of rows&nbsp; &nbsp; m := maxSliceEl(ma.li) - 1&nbsp; &nbsp; fmt.Printf("Cols: %v, Rows: %v\n", m, n)&nbsp; &nbsp; // Set a variable with a structure type for calculating&nbsp;&nbsp; &nbsp; // the amount in a row and indexing each element in it&nbsp; &nbsp; var stringsInfo []strInfo&nbsp; &nbsp; fmt.Println("Initial matrix:")&nbsp; &nbsp; for i := 0; i < n; i++ {&nbsp; &nbsp; &nbsp; &nbsp; sumStrEl := 0&nbsp; &nbsp; &nbsp; &nbsp; for j := 0; j < m; j++ {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; sumStrEl += getEl(i, j, &ma)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; fmt.Print(getEl(i, j, &ma), " ")&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; fmt.Println("|", sumStrEl)&nbsp; &nbsp; &nbsp; &nbsp; // Adding a cell with the sum and index to the slice&nbsp; &nbsp; &nbsp; &nbsp; var strI strInfo&nbsp; &nbsp; &nbsp; &nbsp; strI.summa = sumStrEl&nbsp; &nbsp; &nbsp; &nbsp; strI.pos = i&nbsp; &nbsp; &nbsp; &nbsp; stringsInfo = append(stringsInfo, strI)&nbsp; &nbsp; }&nbsp; &nbsp; fmt.Println("stringsInfo: ", stringsInfo)&nbsp; &nbsp; // Sorting the stringsInfo slice in ascending order of the sum elements&nbsp; &nbsp; sort.Slice(stringsInfo, func(i, j int) (less bool) {&nbsp; &nbsp; &nbsp; &nbsp; return stringsInfo[i].summa < stringsInfo[j].summa&nbsp; &nbsp; })&nbsp; &nbsp; fmt.Println("stringsInfo: ", stringsInfo)&nbsp; &nbsp; fmt.Println("Sorted matrix:")&nbsp; &nbsp; for i := range stringsInfo {&nbsp; &nbsp; &nbsp; &nbsp; for j := 0; j < m; j++ {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // Output the matrix by idnex stringsInfo[i].pos&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; fmt.Print(getEl(stringsInfo[i].pos, j, &ma), " ")&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; fmt.Println("|", stringsInfo[i].summa)&nbsp; &nbsp; }}