如何在O(n)时间内,对0到n的平方减一的n个整数排列

题目详情

▼优质解答

答案和解析

你指的是,将n个数按顺序排列,其中这n个数的范围在0到n的平方减一内吗?
如果是这样,你首先将每个数num化成num= u^2+v的形式（num开方取整求出u,然后v= num-u^2)
然后按照u的不同,将n个数分到n个数组（也可能少于n个数组）.容易知道,u越小,num就越小.所以这里已经把num按u的大小排好了,接着只要对每个数组内部进行排序就行.
也就是在每个数组内,例如每个数组内有i个数,按照v的不同,将i个数分到i个数组,那么v越小,num越小.这样就得出答案了
我这里的数组应该说是链表才对,这样才能做到O(n)时间.
我再重述一下算法的核心思想：首先u越小,num就越小.u相同情况下,v越小,num就越小.

看了如何在O(n)时间内,对0到...的网友还看了以下：

算法分析中O（n）什么含义我知道这是时间复杂度,我想知道O（n）是高阶无穷小的意思吗?是不是说O( 　2020-04-09 …

在二维数组M[0...n,0...m]中,访问某个元素的平均时间复杂度为______。A.O(1)B 　2020-05-23 …

证明o(x^m）+o(x^n）=o(x^m)(x→0)（n>m>0）过程请详细一些,谢谢啦请问其中　2020-06-12 …

如图，点A、B、C在圆O上，AC是圆O的内接正六边形的一边，BC是圆的内接正八边形的一边，AB能否　2020-07-26 …

如何证明n^3sin(nπ/6)=O(n^4)当n接近无限大是正确的大O符号要求是的|n^3sin 　2020-08-01 …

如图1、2、3、……n、M、N分别是圆O的内接正三角形ABC、正方形ABCD、正五边形ABCDE、　2020-08-03 …

已知圆C:x^2+y^2-6x-8y+21=0,点A(1,0),O是坐标原点若以A(1,0)为圆心的　2020-10-31 …

使用mathematica求解多元不等式整数解出错,tt={10.11,14.31,17.48,25 　2020-12-14 …

数据结构试题一、单项选择题（10）1、若长度为n的线性表采用顺序存储结构,在其第i个位置插入一个新元　2021-01-14 …

3.下面算法的时间复杂度为？3.下面算法的时间复杂度为。intf(unsignedintn){if( 　2021-01-14 …

相关搜索：如何在O 对0到n的平方减一的n个整数排列时间内 n