java - 高效的数据结构与算法——自然序列

Question

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

Answer 1

给定行数 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)