给定一个表达式,f(i, j)= 2^i * 5^j,i 和 j 为正整数,使得f(i,j)严格递增,求这个递增序列
思路:和《剑指OFFER》中求丑数的题目很像,序列中第N个数 必然是是前N - 1个数乘以 2 或者乘以5 中大于第N - 1个数的最小值。可以通过分别标记上次乘以2 或乘以5的位置开始寻找被乘数。取最小值,如果 乘以2 的小 则第N个数为该数,同时将2的标记位置右移一位,同理乘以5小时右移5的标记位置,二者相同时同时右移两位。显然,肯定能保证所得数比上一个数大。
public static int[] getSequence(int n) {
if (n <= 0) {
return null;
}
int[] val = new int[n];
val[0] = 1;
int p2 = 0;
int p5 = 0;
for (int i = 1; i < n; i++) {
int val2 = val[p2] * 2;
int val5 = val[p5] * 5;
if (val2 < val5) {
p2++;
val[i] = val2;
} else if (val2 > val5){
p5++;
val[i] = val5;
} else {
val[i] = val2;
p2++;
p5++;
}
}
return val;
}