如何在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到...的网友还看了以下：

电影院的第一排有10个座位,后面一排比紧挨的前面一排多一个座位,该厅最后3排一共有多少个座位第n排有　2020-03-30 …

电影院的第一排有10个座位,后面一排比紧挨的前面一排多一个座位．（1）如果有n排座位,那么该厅第n 　2020-04-27 …

电影院的第一排有12）电影院的第一排有10个座位,后面一排比紧挨的前面一排多一个座位,如果某电影院　2020-04-27 …

(1+1/2)x(1+1/4)x(1+1/6)...（1+1/10）x(1-1/3)x(1-1/5 　2020-05-13 …

】某校为适应电化教学的需要新建阶梯教室,教室的第一排有a个座位,继续看下后面每一排都比前一排多一个　2020-05-16 …

怎么在线上玩N-NAGE？我的N-GAGE平台和游戏都是破解了的，现在想用WIFI连接玩NG、可是　2020-05-17 …

将正整数按如图所示的规律排列下去,若用有序数对（n,m）表示第n排,从左到右第m个,如（4,2）表　2020-05-17 …

电影院的第一排有关10个座位,后面一排比紧的前面一排多一个座位如果有n排座位,那么该厅第n排有几个　2020-05-21 …

第一排1个数,第二排2个数...的数字金字塔,求N行的第一个数和最后一个数.第一排1第二排23第三　2020-06-11 …

第一排1,第二排2,3,第三排4,5,6,第四排7,8,9,10,将正整数按这样的规律排列下去,若　2020-06-11 …

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