leetcode 406. 根据身高重建队列【贪心】
1 | func reconstructQueue(people [][]int) [][]int { |
sort.Slice(people, func(i, j int) bool { ... })
: 使用sort.Slice
对people
进行排序,按照身高从大到小排列,如果身高相同则按照k
从小到大排列。for i, p := range people { ... }
: 遍历排序后的数组,按照每个人的k
值进行插入排序。copy(people[p[1]+1:i+1], people[p[1]:i+1])
: 在插入位置p[1]
之后的位置腾出一个空位,为新的元素插入做准备。people[p[1]] = p
: 将当前人物p
插入到正确的位置。
最终,返回重新排列后的队列 people
。
在 copy(people[p[1]+1:i+1], people[p[1]:i+1])
中,使用 i+1
而不是 len(people)
的原因是为了确保只复制有效的元素范围。这里的目标是将 people[p[1]:i+1]
复制到 people[p[1]+1:i+1]
,而不是复制整个切片。
让我们考虑一下为什么使用 i+1
:
i
表示当前元素的索引,而我们想要复制的范围是从p[1]
到i
。- 使用
i+1
作为结束索引可以确保包含i
在内的元素,而不会超出有效的范围。 - 如果使用
len(people)
作为结束索引,那么将会复制从p[1]
到len(people)-1
的所有元素,这超出了实际有效的范围。
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 Lei Qi's Blog!
评论