Java:检查int中的数字是否按升序排列的快速方法
我正在写一个程序,找到所有在0到整数范围内的Armstrong numbers。最大值。时间限制为10秒。我发现,最耗时的方法是通过只选取数字按升序排列的数字(如果有尾随的零),来缩小要处理的数字范围。在我的机器上运行大约需要57秒。有没有办法让它更快
static boolean isOK(int x)
{
int prev = 0;
while(x > 0)
{
int digit = x % 10;
if((digit > prev || digit == 0) && prev != 0) return false;
x /= 10;
prev = digit;
}
return true;
}
此方法将要处理的数字从2.147.483.647减少到140.990
# 1 楼答案
也许不需要筛选所有整数,只需要按升序建立一组数字。我认为,您可能需要一组字符串(而不是int),因为它更容易构建(通过追加/前置字符递归地构建),然后稍后您只需要单独的“数字”进行功率测试
My take on the problem去长跑。最大值(19位)在大约6秒钟内,在大约一小时内一直到39位
# 2 楼答案
下面的代码运行x4的速度与原始代码一样快(在我的笔记本电脑上运行3秒),并打印
140990 in 3 sec.
方法isOK
不变# 3 楼答案
这里几乎没有可优化的代码。你的时间问题可能在别处。然而,我想到了一种技巧,那就是Memoization
这个技巧使用
Set
来记住所有正确的数字,这样你就不需要检查它们了。您还可以保留Set
个失败的整数,以避免再次检查它们,但保留集合中的所有整数可能会破坏某些东西# 4 楼答案
下面的代码不处理尾随的零,但值得检查它在性能方面是否有希望