[Leetcode][441. 排列硬币] 4种解法：暴力，二分查找，数学，位运算

By Long Luo

Leetcode 441. 排列硬币 的题解，有4种解决方法，前3种比较容易想到，位运算 比较难想到。

方法一：暴力

思路和算法

模拟硬币排列过程，从$ans = 1$开始，逐行$ans + 1$，当硬币不足排列当前行时退出，注意返回时需要$ans - 1$，因为在排列完上一行时已经$+1$了，返回时需要$-1$。

// BF O(sqrtn) O(1)
public int arrangeCoins_bf(int n) {
	int ans = 1;
	while (n >= ans) {
		n -= ans;
		ans++;
	}

	return ans - 1;
}

复杂度分析

• 时间复杂度：$O(\sqrt{n})$，因为总行数一定不超过$2(\sqrt{n}+1)$。
• 空间复杂度：$O(1)$。

方法二：二分查找

思路和算法

第$i$行必须有$i$个硬币（最后一行除外），总行数的增加所需要的硬币数是单调递增的，到第$i$行时总共使用的硬币数量为$total = \frac{i \times (i + 1)}{2}$，我们的目标是寻找一个$i$使得$total \leq n$，可以利用二分加速在$1$到$\frac{n + 1}{2}$之间查找。

// BS O(logn) O(1)
public int arrangeCoins_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$行放满一共可以得到$\frac{(x + 1) \times x}{2}$个硬币，则有：

$\frac{(x + 1) \times x}{2} = n$

整理得一元二次方程

$x^2 + x - 2n = 0$

因为$n \ge 1$，所以判别式

$\Delta = b^2 - 4ac = 8n + 1 > 0$

解得$x_1 = \frac{-1 - \sqrt{8n + 1}}{2}$, $x_2 = \frac{-1 + \sqrt{8n + 1}}{2}$

$x_1 < 0$，舍去不用，$x_2$即为硬币可以排列成的行数。

因为需要可以完整排列的行数，所以需要向下取整。

// Math O(1) O(1)
public int arrangeCoins_math(int n) {
	int val = (int) (Math.sqrt((long) 8 * n + 1) - 1);
	return val / 2;
}

复杂度分析

• 时间复杂度：$O(1)$。
• 空间复杂度：$O(1)$。

方法四：位运算

思路与算法：

1. 因为$1 \leq n \leq 2^{31} - 1$，那么最长的数是$31$位，显然$sqrt(2^{31} - 1) = log(sqrt(2^{31} - 1)) = 16$，也就是说答案最长也不会超过$16$位；
2. 创建一个$mask$，第$15$位设为$1$，其余为$0$；
3. 先依次给$ans$按位从高到低设$1$，检查$ans \times (ans + 1) > n$，$ans = 0$；
4. mask依次右移，直至$0$，即为我们的答案。

代码如下所示：

// Bit O(1) O(1)
public static int arrangeCoins_bit(int n) {
    int mask = 1 << 15;
    long ans = 0;
    while (mask > 0) {
        ans |= mask;
        if (ans * (ans + 1) / 2 > n) {
            ans ^= mask;
        }
        mask >>= 1;
    }

    return (int) ans;
}

复杂度分析

• 时间复杂度：$O(1)$。
• 空间复杂度：$O(1)$。

---

All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗