星际穿越-二分法

1 暴力破解，时间复杂度为o( )
import java.util.;
public class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
while(sc.hasNext()){
long n=sc.nextLong();
long h=(long)Math.sqrt(n)+1;
for(long i=h;i>=0;i--){
if(ii+i<=n){
System.out.println(i);
return;
}
}
}
}
}
2 二分法,时间复杂度为o(logn)

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            long n=sc.nextLong();
            long l=0;
            long h=(long)Math.sqrt(n)+1;
            while(l+1<h){
                long mid=l+(h-l)/2;
                if(mid*mid+mid>n) h=mid;
                else l=mid;
            }
            if(h*h+h<n){
                System.out.println(h);
            }
            else{
                System.out.println(l);
            }
        }
    }
}

3 数学法,时间复杂度为o(1)

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            long h=sc.nextLong();
           System.out.println((long)(Math.sqrt(1+4*h)-1)/2);
        }
    }
}