2021-10-10 LeetCode441-排列硬币（每日一题）

题目所给阶梯状的排列方式为等差数列，我们可以很轻易的计算出不同的阶梯行数排满对应的硬币总数，我最开始的想法就是让K自增，同时比较当前K对应的硬币总数与题给N的大小，可以很轻松找出结果。

但是显然时间效率很低，上代码！

class Solution
{
public:
    int arrangeCoins(int n)
    {
        long long sum = 1, k = 1; //long long防止数据溢出
        if (n == 0)
            return 0;
        while (sum < n)
        //累加K，每次计算等差数列的和与n比较
        {
            k++;
            sum = k * (1 + k) / 2;
        }
        //对于最后一行是否占满进行判别
        if (sum == n)
            return k;
        else
            return k - 1;
    }
};

考虑如何在时间反面进行优化，正如方法一所说K自增实际上就相当于一个数组按照索引的遍历，我们在查找一个符合条件的值，这样我们就可以在查找阶段进行优化。我们使用二分查找法代替顺序查找

代码如下

class Solution
{
public:
    int arrangeCoins(int n)
    {
        //还是要注意数据类型的定义，防止溢出
        long long left = 1, right = n, mid;
        while (left < right)
        {
            mid = (left + right) / 2 + 1;
            //观察到我们要找的数字是向下取整，所以中间值我们设定为向上取整，避免特殊情况死循环
            if ((long long)mid * (1 + mid) / 2 > n)
            {
                right = mid - 1;
            }
            else if ((long long)mid * (1 + mid) / 2 < n)
            {
                left = mid;
            }
            else
                return mid;
        }
        return left;
    }
};