java - Codility FrogJmp奇怪的Java分数

因此，我决定尝试Codility。第一个任务-FrogJmp非常简单，但是令我惊讶的是我得到了44％的成绩。就性能而言，即使是正确的解决方案也显然是 Not Acceptable 。

原始解决方案:

public int solution2(int X, int Y, int D) {
    return (int) Math.ceil((float)(Y -X)/D);
}

因此，我决定尝试使用其他代码，而不使用浮点算法。

public int solution(int X, int Y, int D) {
    int diff = Y - X;
    if (diff % D == 0)
        return diff /D;
    else
        return diff/D + 1;

}

这次我得到了100％。因此，我想亲自检查性能并编写简单的测试:

class Solution {


    public int solution(int X, int Y, int D) {
        int diff = Y - X;
        if (diff % D == 0)
            return diff /D;
        else
            return diff/D + 1;

    }

    public int solution2(int X, int Y, int D) {
        return (int) Math.ceil((float)(Y -X)/D);
    }


    private static Random ran = new Random(System.currentTimeMillis());

    public static int getRandom(int a, int b){
        return ran.nextInt(b - a + 1) + a;
    }


    public static void main(String[] args) {

        int size = 1000_000;
        int max = 1000_000_000;

        int[] xs = new int[size];
        int[] ys = new int[size];
        int[] ds = new int[size];

        for (int i = 0; i < size; i++) {
            int y = getRandom(1, max);
            int x = getRandom(1, y);
            int d = getRandom(1, max);
            xs[i] = x;
            ys[i] = y;
            ds[i] = d;
        }

        long start = System.nanoTime();

        Solution sol = new Solution();
        for (int i = 0; i < size; i++) {
            sol.solution2(xs[i], ys[i], ds[i]);
        }

        long diff = System.nanoTime() - start;

        System.out.println("took: " + diff/1000000 + "ms");
    }
}

令我惊讶的是，在我的机器上，解决方案1平均花费13毫秒，而解决方案2(据报道绝对无效)花费10毫秒。

我想念什么？

也许它必须在预期的任务时间和空间复杂度上做一些事情。



解决方案2是否具有恒定的时间和空间复杂性？

另外，对于44％的解决方案，我无法理解此结果报告:

这是什么意思？？

最佳答案

两种解决方案都具有O(1)时间复杂度。问题是第一个解决方案返回错误的答案。性能测试测试答案和时间。您的解决方案失败可能是由于使用浮点数引起的精度问题。

对于x = 1，y = 1000000000，d = 1，您的第一个解决方案给出1000000000作为答案，第二个解决方案给出
999999999。从(float)更改为(double)可更正此结果。

在这些算法测试中，通常最好避免使用浮点运算，以便更轻松地获得所有情况的准确答案。