0315. Count of Smaller Numbers After Self

315. Count of Smaller Numbers After Self #

题目 #

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Example:

Input: [5,2,6,1]
Output: [2,1,1,0] 
Explanation:
To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.

题目大意 #

给定一个整数数组 nums,按要求返回一个新数组 counts。数组 counts 有该性质: counts[i] 的值是  nums[i] 右侧小于 nums[i] 的元素的数量。

示例:


输入: [5,2,6,1]
输出: [2,1,1,0] 
解释:
5 的右侧有 2 个更小的元素 (2 和 1).
2 的右侧仅有 1 个更小的元素 (1).
6 的右侧有 1 个更小的元素 (1).
1 的右侧有 0 个更小的元素.

解题思路 #

  • 给出一个数组,要求输出数组中每个元素相对于数组中的位置右边比它小的元素。
  • 这一题是第 327 题的缩水版。由于需要找数组位置右边比当前位置元素小的元素,所以从数组右边开始往左边扫。构造一颗线段树,线段树里面父节点存的是子节点出现的次数和。有可能给的数据会很大,所以构造线段树的时候先离散化。还需要注意的是数组里面可能有重复元素,所以构造线段树要先去重并排序。从右往左扫的过程中,依次添加数组中的元素,添加了一次就立即 query 一次。query 的区间是 [minNum, nums[i]-1]。如果是 minNum 则输出 0,并且也要记得插入这个最小值。这一题的思路和第 327 题大体类似,详解可见第 327 题。
  • 这一题同样可以用树状数组来解答。相比 327 题简单很多。第一步还是把所有用到的元素放入 allNums 数组中,第二步排序 + 离散化。由于题目要求输出右侧更小的元素,所以第三步倒序插入构造树状数组,Query 查询 [1,i-1] 区间内元素总数即为右侧更小元素个数。注意最终输出是顺序输出,计算是逆序计算的,最终数组里面的答案还需要逆序一遍。相同的套路题有,第 327 题,第 493 题。

代码 #


package leetcode

import (
	"sort"

	"github.com/halfrost/leetcode-go/template"
)

// 解法一 线段树
func countSmaller(nums []int) []int {
	if len(nums) == 0 {
		return []int{}
	}
	st, minNum, numsMap, numsArray, res := template.SegmentCountTree{}, 0, make(map[int]int, 0), []int{}, make([]int, len(nums))
	for i := 0; i < len(nums); i++ {
		numsMap[nums[i]] = nums[i]
	}
	for _, v := range numsMap {
		numsArray = append(numsArray, v)
	}
	// 排序是为了使得线段树中的区间 left <= right,如果此处不排序,线段树中的区间有很多不合法。
	sort.Ints(numsArray)
	minNum = numsArray[0]
	// 初始化线段树,节点内的值都赋值为 0,即计数为 0
	st.Init(numsArray, func(i, j int) int {
		return 0
	})
	for i := len(nums) - 1; i >= 0; i-- {
		if nums[i] == minNum {
			res[i] = 0
			st.UpdateCount(nums[i])
			continue
		}
		st.UpdateCount(nums[i])
		res[i] = st.Query(minNum, nums[i]-1)
	}
	return res
}

// 解法二 树状数组
func countSmaller1(nums []int) []int {
	// copy 一份原数组至所有数字 allNums 数组中
	allNums, res := make([]int, len(nums)), []int{}
	copy(allNums, nums)
	// 将 allNums 离散化
	sort.Ints(allNums)
	k := 1
	kth := map[int]int{allNums[0]: k}
	for i := 1; i < len(allNums); i++ {
		if allNums[i] != allNums[i-1] {
			k++
			kth[allNums[i]] = k
		}
	}
	// 树状数组 Query
	bit := template.BinaryIndexedTree{}
	bit.Init(k)
	for i := len(nums) - 1; i >= 0; i-- {
		res = append(res, bit.Query(kth[nums[i]]-1))
		bit.Add(kth[nums[i]], 1)
	}
	for i := 0; i < len(res)/2; i++ {
		res[i], res[len(res)-1-i] = res[len(res)-1-i], res[i]
	}
	return res
}


⬅️上一页

下一页➡️

Calendar Apr 8, 2023
Edit Edit this page
本站总访问量:  次 您是本站第  位访问者