离散化

3 -1 2 -2 这个数列有 5个逆序对

4 2 3 1 也是五个

我们把最小的-2视作1

第二的-1看做2

法一(推荐):

结构体保存数组num 和它在原数组里的下标

{3,1}{-1,2}{2,3}{-2,4}

然后按数字大小排序

{-2,4}{-1,2}{2,3}{3,1}

现在我们就得到了 4 2 3 1了。

法二:

将原数组a复制得到b

将b排序,然后用二分去找a中的元素在b中的下标

Original: https://www.cnblogs.com/29taorz/p/15382676.html
Author: T_X蒻
Title: 离散化

原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/644223/

转载文章受原作者版权保护。转载请注明原作者出处!

(0)

大家都在看

亲爱的 Coder【最近整理,可免费获取】👉 最新必读书单  | 👏 面试题下载  | 🌎 免费的AI知识星球