// BS O(logn) O(1) publicintarrangeCoins_bs(int n){ long left = 1; long right = ((long) n + 1) / 2; while (left < right) { long mid = left + (right - left + 1) / 2; long sum = mid * (mid + 1) / 2; if (sum <= n) { left = mid; } else { right = mid - 1; } }
return (int) left; }
复杂度分析
时间复杂度:O(logn)。
空间复杂度:O(1)。
方法三:数学
思路和算法
第x行放满一共可以得到2(x+1)×x个硬币,则有:
2(x+1)×x=n
整理得一元二次方程
x2+x−2n=0
因为n≥1,所以判别式
Δ=b2−4ac=8n+1>0
解得x1=2−1−8n+1, x2=2−1+8n+1
x1<0,舍去不用,x2即为硬币可以排列成的行数。
因为需要可以完整排列的行数,所以需要向下取整。
1 2 3 4 5
// Math O(1) O(1) publicintarrangeCoins_math(int n){ int val = (int) (Math.sqrt((long) 8 * n + 1) - 1); return val / 2; }