Codility FrogJmp 奇怪的 Java 得分

Question

所以我决定尝试Codility。第一个任务 - FrogJmp非常简单，但令我惊讶的是我的得分为 44%。解决方案，即使正确在性能方面显然是不可接受的。

原解决方案：

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 毫秒。

我错过了什么？

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

预期的最坏情况时间复杂度为 O(1)；预期的最坏情况空间复杂度为 O(1)。

解决方案 2 不是具有恒定的时间和空间复杂度吗？

此外，我无法理解 44% 解决方案的结果报告：

这是什么意思？？

Answer 1

两种解决方案的时间复杂度均为 O(1)。问题是第一个解决方案返回错误的答案。性能测试测试答案以及时间。您的解决方案失败可能是因为使用浮点数的精度问题。

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

在这些算法测试中，通常最好尽可能避免浮点运算，以便更容易获得所有情况的准确答案。