java codility 青蛙河一号

Question

我一直在尝试解决 Codility 网页上的 Java 练习。

以下是上述练习和我的解决方案的链接。

https://codility.com/demo/results/demoH5GMV3-PV8

谁能告诉我可以在我的代码中更正什么以提高分数？

以防万一这里是任务描述：

一只小青蛙想要到达河的另一边。青蛙目前位于位置 0，想要到达位置 X。树叶从树上落到河面上。

给定一个非空的零索引数组 A，其中包含 N 个表示落叶的整数。 A[K] 代表一片叶子在时间 K 落下的位置，以分钟为单位。

目标是找出青蛙最早可以跳到河对岸的时间。只有当从 1 到 X 过河的每个位置都出现树叶时，青蛙才能过河。

例如，给定整数 X = 5 和数组 A，使得：

   A[0] = 1
  A[1] = 3
  A[2] = 1
  A[3] = 4
  A[4] = 2
  A[5] = 3
  A[6] = 5
  A[7] = 4

第6分钟，一片树叶落到5号位置，这是河对岸各位置出现树叶最早的时间。

写一个函数：

 class Solution { public int solution(int X, int[] A); }

即，给定一个由 N 个整数和整数 X 组成的非空零索引数组 A，返回青蛙可以跳到河对岸的最早时间。

如果青蛙永远无法跳到河的另一边，函数应该返回-1。

例如，给定 X = 5 和数组 A 使得：

   A[0] = 1
  A[1] = 3
  A[2] = 1
  A[3] = 4
  A[4] = 2
  A[5] = 3
  A[6] = 5
  A[7] = 4

如上所述，该函数应返回 6。假使，假设：

 N and X are integers within the range [1..100,000];
each element of array A is an integer within the range [1..X].

复杂：

 expected worst-case time complexity is O(N);
expected worst-case space complexity is O(X), beyond input storage (not counting the storage required for input arguments).

可以修改输入数组的元素。

这是我的解决方案：

 import java.util.ArrayList;
import java.util.List;

class Solution {

    public int solution(int X, int[] A) {
        int list[] = A;
        int sum = 0;
        int searchedValue = X;

        List<Integer> arrayList = new ArrayList<Integer>();

        for (int iii = 0; iii < list.length; iii++) {

            if (list[iii] <= searchedValue && !arrayList.contains(list[iii])) {
                sum += list[iii];
                arrayList.add(list[iii]);
            }
            if (list[iii] == searchedValue) {
                if (sum == searchedValue * (searchedValue + 1) / 2) {
                    return iii;
                }
            }
        }
        return -1;
    }
}

原文由 pshemek 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

您在循环中使用 arrayList.contains ，这将不必要地遍历整个列表。

这是我的解决方案（我前一段时间写的，但我相信它的得分是 100/100）：

     public int frog(int X, int[] A) {
        int steps = X;
        boolean[] bitmap = new boolean[steps+1];
        for(int i = 0; i < A.length; i++){
            if(!bitmap[A[i]]){
                bitmap[A[i]] = true;
                steps--;
                if(steps == 0) return i;
            }

        }
        return -1;
    }

原文由 rafalio 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

这是我的解决方案。它让我得到了 100/100：

 public int solution(int X, int[] A)
{
     int[] B = A.Distinct().ToArray();
     return (B.Length != X) ? -1 : Array.IndexOf<int>(A, B[B.Length - 1]);
}

原文由 Kamlesh Shewani 发布，翻译遵循 CC BY-SA 3.0 许可协议