题目

小知识点:链表转数组

res := [][]int{}
// 把链表转为数组
for e:=l.Front();e!=nil;e=e.Next(){
    // 要断言,因为这个特殊,二维数组,所以断言为[]int
    res = append(res, e.Value.([]int))
}

leeocode:406

代码与解析

题目给定的是一个二维数组, 两个维度,

应该先确定一个维度,再按照另一个维度重新排列


这里先确定一个维度, 先确定身高维度,然后再按照索引重新插入,这里设置的很巧
具体查看链接

他这个身高一定是大体趋势是从高到矮的,偶尔有矮的按索引插入

// 数组解法
func reconstructQueue(people [][]int) [][]int {
    //先将身高从大到小排序,确定最大个子的相对位置
    sort.Slice(people,func(i,j int)bool{
        // 身高相同时, 将K按照从小到大排序
        if people[i][0]==people[j][0]{
            return people[i][1]<people[j][1]
        }
        // 确保身高按照从大到小顺序排序
        return people[i][0]>people[j][0]
    })
    // 再按照K进行插入排序,优先插入K小的
    result := make([][]int, 0)
    for _, info := range people {
        // info是一维数组 【7,0】 【7,1】
        result = append(result, info)
        // 这里不是people数组,
        // 这里要将插入位置之后的元素后移一位,腾出空间
        copy(result[info[1] +1:], result[info[1]:])
        result[info[1]] = info// 指定位置插入元素
    }
    return result
}

// 链表解法
// 用list实现
func reconstructQueue(people [][]int) [][]int {
    // 排序
     sort.Slice(people,func (i,j int) bool {
        if people[i][0]==people[j][0]{
            return people[i][1]<people[j][1]//当身高相同时,将K按照从小到大排序
        }
         //先将身高从大到小排序,确定最大个子的相对位置
        return people[i][0]>people[j][0]
    })
    // 创建链表
    l:=list.New()
    for i:=0;i<len(people);i++{
        position:=people[i][1]      // 取索引, 【7,1】取 1
        mark:=l.PushBack(people[i]) // 插入元素并把元素返回,这里的插入的是 每一个一维数组, 【7,1】,类似这样
        e:=l.Front()                // 取链表第一个元素

        for position!=0{            // 获取相对位置
            position--
            e=e.Next()              // 一直往下找,找到插入的合适位置
        }
        l.MoveBefore(mark,e)        // 移动位置,把mark移动到e前面
    }
    res:=[][]int{}
    // 把链表转为数组
    for e:=l.Front();e!=nil;e=e.Next(){
        res=append(res,e.Value.([]int))
    }
    return res
}

站点统计

  • 文章总数:315 篇
  • 分类总数:20 个
  • 标签总数:193 个
  • 运行天数:1147 天
  • 访问总数:26842 人次

浙公网安备33011302000604

辽ICP备20003309号