排列硬币 | Shinuye Site

# 题目描述

你总共有 n 枚硬币，你需要将它们摆成一个阶梯形状，第 k 行就必须正好有 k 枚硬币。

给定一个数字 n，找出可形成完整阶梯行的总行数。

n 是一个非负整数，并且在32位有符号整型的范围内。

# 示例

n = 5

硬币可排列成以下几行:
¤
¤ ¤
¤ ¤

因为第三行不完整，所以返回2.

n = 8

硬币可排列成以下几行:
¤
¤ ¤
¤ ¤ ¤
¤ ¤

因为第四行不完整，所以返回3.

n = 6

硬币可排列成以下几行: ¤
¤ ¤
¤ ¤ ¤
返回3.

# 算法设计

这个题在LeetCode里面的标签是简单的二分搜索，当我读完题目的时候，还没有想到用二分法如何求解，但是我想到了一种相对暴力的解法，于是就写了一段，调试了几次通过了。具体代码如下暴力法1。因为对于二分法没有思路，所以我去搜索了一下，结果看到一个更加直观的暴力法，一看就能理解，对比于我的代码，可读性更好。所以我把另一个暴力法总结在暴力法2中。
二分法主要利用到的就是等差数列求和这个性质，求和的过程要注意数据不能溢出，所以定义的时候使用了long型。

# 代码

暴力法1：

int arrangeCoins(int n) {
	int i = 0;
	while (n > i) {
		n = n - i;  //每一行都需要减去当前行数个硬币
		i++;		//行数加1
		if (n == i) {    //特例，刚好最后一行放完所有的硬币，如6个硬币的时候，能放3行
			i++;
		}
	}
	return i - 1;
}

1
2
3
4
5
6
7
8
9
10
11

暴力法2：

int arrangeCoin(int n) {
	int res = 0;  //存储结果
	while (n > 0) {
		res++;
		n = n - res;
	}
	//刚好减完的话n=0，例如6-1-2-3 = 0 此时返回3
	//当减完小于0，例如5-1-2-3 < 0 此时返回2
	if (n == 0) {
		return res;
	}
	else {
		return res - 1;
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

二分搜索：

int arrangeCoins(int n) {
	int left = 0, right = n;
	long mid, sum;
	while (left <= right) {
		mid = left + (right - left) / 2;
		//等差数列求和
		sum = (1 + mid) * mid / 2;
		if (sum == n) {
			return (int)mid;
		}
		else if (sum < n) {
			left = mid + 1;
		}
		else {
			right = mid - 1;
		}
	}
	return left -1;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 复杂度分析

时间复杂度：
暴力法中，提交时用时16ms，算法执行效率不高，时间复杂度为O(n)。
二分搜索中，算法的时间复杂度为O(logn);

空间复杂度：
暴力法中，也没有占用多余的内存，只是定义了一个变量，空间复杂度为O(1)。
二分搜索中，空间复杂度为O(1);