1 - 1
2 - 2,3
3 - 4,5,6
4 - 7,8,9,10
给定从 4 到 6 的任意数字，我需要输出为 3。
给定 7 到 10 之间的任意数字，我需要输出为 4。
我需要上述问题的最快解决方案来解决算法。
我能想到的是暴力算法:
给定 7:
n-square + n = 7*2 = 14
1 + 1 = 2 < 14
4 + 2 = 6 < 14
9 + 3 = 12 < 14
16+ 4 = 20 >=14 --> So 4
是否有更好的方法来得出解决方案？或者我对算法本身的方法有缺陷？
算法的简要说明:
A,B,C
每次迭代后，每个元素都会增加 1。
A,A,B,B,C,C
给定 3，将返回 C。
给定 4 或 5，将返回 A。
给定 6 或 7，将返回 B。
给定 8 或 9，将返回 C。
给定 10 或 11 或 12，将返回 A。
给定 13 或 14 或 15，将返回 B。
数学问题的解决方案将如何帮助解决算法:
Total number of elements = 3
Given number = 13 (Output to be B)
Divide and Ceiling = Ceil (13/3) = 5 [So 13 falls under when every element has become * 3] (From Mathematical problem : If given number is 5, 3 is to be used)
Starting index of when every element has become * 3 [IS_EQUAL_TO = ] 3 * 3(summation of previous iteration => 1 + 2) + 1 = 10
To Find the index = Ceil(13-10+1/3 (this 3,comes from the mathematical problem) ) = Ceil (4/3) = 2nd index = B
最佳答案
给定行数 N，三角形的大小为 N(N+1)/2。您实际上是在尝试找到最小整数 N，使得 N(N+1)/2 >= M，其中 M 已给定。如果您有计算平方根的函数，则可以在常数时间内求解该方程。
N(N+1)/2 >= M，两边都乘以2，
N²+N >= 2M，求平方，求平方根，blablabla
N >= sqrt(2M+1/4)-1/2
因此答案是 N = ceil(sqrt(2*M + .25) - .5)
关于java - 高效的数据结构与算法——自然序列，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/35825670/