根据索引查找金字塔的行？

给定一个像这样的金字塔：

      0
     1 2
    3 4 5
   6 7 8 9
     ...

并给出金字塔的索引i where i代表i金字塔的第一个数字，有没有办法找到金字塔的行的索引i第一个元素属于？ （例如，如果i = 6,7,8,9，它位于第 3 行，从第 0 行开始）

There's a connection between the row numbers and the triangular numbers. The nth triangular number https://en.wikipedia.org/wiki/Triangular_number, denoted T_n, is given by T_n = n(n-1)/2. The first couple triangular numbers are 0, 1, 3, 6, 10, 15, etc., and if you'll notice, the starts of each row are given by the nth triangular number (the fact that they come from this triangle is where this name comes from.)

So really, the goal here is to determine the largest n such that T_n ≤ i. Without doing any clever math, you could solve this in time O(√n) by just computing T₀, T₁, T₂, etc. until you find something bigger than i. Even better, you could binary search for it in time O(log n) by computing T₁, T₂, T₄, T₈, etc. until you overshoot, then binary searching on the range you found.

或者，我们可以尝试直接解决这个问题。假设我们想要找到 n 的选择，使得

n(n + 1) / 2 = 我

展开，我们得到

n² / 2 + n / 2 = i.

等价地，

n² / 2 + n / 2 - i = 0,

或者，更容易：

n² + n - 2i = 0.

现在我们使用二次公式：

n = (-1 ± √(1 + 8i)) / 2

负根我们可以忽略，所以我们想要的n的值为

n = (-1 + √(1 + 8i)) / 2。

该数字不一定是整数，因此要找到所需的行，我们只需向下舍入：

行 = ⌊(-1 + √(1 + 8i)) / 2⌋。

In code:

int row = int((-1 + sqrt(1 + 8 * i)) / 2);

让我们通过测试一下来确认它是否有效。 9去哪儿了？嗯，我们有

(-1 + √(1 + 72)) / 2 = (-1 + √73) / 2 = 3.77

向下舍入，我们看到它位于第 3 行 - 这是正确的！

再试试，55 去哪儿了？出色地，

(-1 + √(1 + 440)) / 2 = (√441 - 1) / 2 = 10

So it should go in row 10. The tenth triangular number is T₁₀ = 55, so in fact, 55 starts off that row. Looks like it works!