问了问还是解决不了,我(入门)

编写程序求满足1+2+3+4+…+n>=10000 的最小的正整数n为多少。

看到这个题目感觉有点意思,O(n)的解法容易实现,已经有其它答案写了就不再重复了。下面是用“二分查找”思想写的时间复杂度为O(log(n))的解法,仅供参考。自测输入10000的话答案是141.

public class MinN {
    public static void main(String[] args) {
        int target = 10000; //目标值
        int ans = findN(target);
        System.out.println(ans);
    }

    /**
     * 二分查找
     * */
    public static int findN(int target) {
        int i = 1,j = target;
        while (i <= j) {
            int mid = (i + j) / 2;
            long tmp = sum(1,mid);
            if(tmp >= target) {
                if(sum(1,mid) < target) {
                    return mid;
                } else {
                    j = mid - 1;
                }
            } else {
                i = mid + 1;
            }
        }
        return i;
    }

    /**
    * 求从start加到end的和。使用long类型避免计算后超出整数范围
    * */
    public static long sum(int start,int end) {
        return (long) (end - start + 1) * (long) (start + end) / 2;
    }
}

提供一个大致思路供参考,复杂度O(1)。
推公式,解方程,判断情况,结果向上取整。
n * (n + 1) / 2 = 10000

public class Main {
    public static void main(String[] args) {  
        int sum = 0, n = 0;
        while(true) {
            sum += ++n;
            if(sum > 10000) {
                break;
            }
        }
        System.out.println(n);
    }
}