从Leetcode 每日一题练习继续讨论：
1122. 数组的相对排序
1122. Relative Sort Array
题解
考虑数组中数字的大小范围在1000以内, 因此直接对数组排序可以使用计数排序算法. 本题中要求将数组1中的数字按照数组2中数字的顺序排序, 这部分也可以使用计数排序的思想, 即统计数组1中各个数的出现次数, 并保存在一个计数数组中, 这个数组中下标i处的值为数字i对应的数组1中出现的次数. 这种用下标指示值, 用元素指示个数的思路在前面的题中也多次出现. 得到计数数组后, 先将数组中包含在arr2的数按照arr2中的顺序放置, 并将对应位置次数归零, 再从头遍历数组, 按升序将其余数字放在末尾即可. 关于计数排序可参考
代码
func relativeSortArray(arr1 []int, arr2 []int) []int {
count := make([]int, 1001)
for _,value := range arr1{
count[value]++
}
result := []int{}
for _,value := range arr2{
for count[value]>0{
result = append(result, value)
count[value]--
}
}
for index,value := range count{
for value > 0{
result = append(result, index)
value--
}
}
return result
}