《LeetCode之每日一题》:174.排列硬币

有关题目

你总共有 n 枚硬币，并计划将它们按阶梯状排列。
对于一个由 k 行组成的阶梯，其第 i 行必须正好有 i 枚硬币。
阶梯的最后一行 可能 是不完整的。

给你一个数字 n ，计算并返回可形成 完整阶梯行 的总行数。

提示：

1 <= n <= 2^31 - 1

题解

法一：迭代
代码一：

//n - ans 表示n 减去 上一次答案,必须要大于等于 1，这样根据阶梯的递增加一，才有满足条件的新的一行阶梯
class Solution {
public:
    int arrangeCoins(int n) {
        int ans = 0;
        while(n - ans > 0)
        {
            n -= ++ans;
        }

        return ans;
    }
};

代码二：

//sum > n跳出循环，由于++i，所以跳出循环的i 先 减去 1，由于sum > n 说明上一步的sum += i中的i 太大了，故再减一
class Solution {
public:
    int arrangeCoins(int n) {
        int i = 1;
        long sum = 0;

        while(sum <= n)
        {
            sum += i;
            ++i;
        }

        return i - 2;
    }
};

时间复杂度：O(n)
空间复杂度：O(1)

法二：二分查找
参考
Tips

等差数列求和公式变形

class Solution {
public:
    int arrangeCoins(int n) {
        int l = 1, r = n;
        while(l < r)
        {
            long mid = l + (r - l + 1) / 2;
            if ((long long)mid * (mid + 1) <= (long long)2 * n)
                l = mid;
            else 
                r = mid - 1;
        }

        return l;
    }
};

class Solution {
public:
    int arrangeCoins(int n) {
        return (int)((sqrt((long long)n * 8 + 1) - 1) / 2);
    }
};

时间复杂度：sqrt跟CPU指令有关，这里不做研究
空间复杂度：O(1)