描述如果一个数只有质数因子2,3,5,那么这个数是一个丑数。
前10个丑数分别为1,2,3,4,5,6,8,9,10,12,
找出第 N 个丑数
每次for循环只执行一次,我认为复杂度应该是O(n),有没有大佬解惑一下
public class Demo04 {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int number = ChouShu(input.nextInt());
System.out.println(number);
}
public static int ChouShu(int n) {
if(n<=0) {
System.out.println("输入有误!");
return -1;
}
if(n==1) {
return 1;
}
int k=3,count=1;
for(int i=2;i<k;i++) {
if(i%2==0 || i%3==0 || i%5==0) {
count++;
if(count==n) {
return i;
}
}
k++;
}
return -1;
}
}
为1也是一个丑数
是O(n),这种时间复杂度的表示方法叫做大O表示法,这种表示时间复杂度的方法首先是一个近似值,他会忽略系数,也会忽略常数,所以你这种求解,就是O(n)
O(n)
时间复杂度求得是最差情况,你这个程序最差得情况是:走一遍for循环,里面的if都没有通过,那么最多就是走了一遍数组长度。所以时间复杂度就是O(n)