<分区>
有如下顺序:
101001000100001...
如何定义一个方法,获取序列中元素的索引并返回该元素的值(0或1)?
public Element getValue(int index) {}
也许需要使用递归?如果有任何想法,我将不胜感激!
<分区>
有如下顺序:
101001000100001...
如何定义一个方法,获取序列中元素的索引并返回该元素的值(0或1)?
public Element getValue(int index) {}
也许需要使用递归?如果有任何想法,我将不胜感激!
最佳答案
小点表示这个系列会继续。所以这是您的解决方案:
让我们考虑基于 1 的索引。您注意到 1 出现在索引 1 处,(1+2)=3, (1+2+3)=6, (1+2+3+4)=10 等。我们有一个公式。它是 n*(n+1)/2 。
因此对于给定的索引(现在这是基于 0 的,因为 java 数组从索引 0 开始)执行以下操作:
index = index + 1; // now it is 1 based index and our formula would fit in nicely.
index = index * 2;
sqroot = integer part of square root of index;
if( sqroot * (sqroot+1) == index)
print 1;
else
print 0;
也不需要递归,因为这是 O(1) 的解决方案(不考虑平方根函数的复杂性)
关于java - 查找序列元素值的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14910972/