我的代码的哪一部分使我的性能受到影响？（Codility 的 MaxCounter）

Question

我有以下问题：

你有 N 个计数器，初始设置为 0，你可以对它们进行两种可能的操作：

    increase(X) − counter X is increased by 1,
    max counter − all counters are set to the maximum value of any counter.

给出了一个由 M 个整数组成的非空零索引数组 A。该数组表示连续操作：

    if A[K] = X, such that 1 ≤ X ≤ N, then operation K is increase(X),
    if A[K] = N + 1 then operation K is max counter.

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

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

每次连续操作后的计数器值为：

(0, 0, 1, 0, 0)
(0, 0, 1, 1, 0)
(0, 0, 1, 2, 0)
(2, 2, 2, 2, 2)
(3, 2, 2, 2, 2)
(3, 2, 2, 3, 2)
(3, 2, 2, 4, 2)

目标是计算所有操作后每个计数器的值。

写一个函数：

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

给定一个整数 N 和一个由 M 个整数组成的非空零索引数组 A，returns 是一个表示计数器值的整数序列。

例如，给定：

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

函数应该 return [3, 2, 2, 4, 2]，如上所述。

假设：

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

复杂度：

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

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

我已经使用以下代码回答了这个问题，但尽管时间复杂度为 O(N+M)，但只获得了 80% 而不是 100% 的性能：

public class Solution {

    public int[] solution(int N, int[] A) {

        int highestCounter = N;
        int minimumValue = 0;
        int lastMinimumValue = 0;
        int [] answer = new int[N];

        for (int i = 0; i < A.length; i++) {
            int currentCounter = A[i]; 
            int answerEquivalent = currentCounter -1;

            if(currentCounter >0 && currentCounter<=highestCounter){
                answer[answerEquivalent] = answer[answerEquivalent]+1; 

                if(answer[answerEquivalent] > minimumValue){
                    minimumValue = answer[answerEquivalent];
                }
            }

            if (currentCounter == highestCounter +1 && lastMinimumValue!=minimumValue){
                lastMinimumValue = minimumValue;
                Arrays.fill(answer, minimumValue);
            }
        }
        return answer;
    }

}

我在这里的表现哪里有问题？该代码给出了正确的答案，但尽管具有正确的时间复杂度，但仍未达到规范。

Answer 1

下面的操作是O(n)次：

Arrays.fill(answer, minimumValue);

现在，如果给你一个测试用例，其中经常重复 max counter 操作（比如总操作的 n/3）——你得到了一个 O(n*m) 算法（最差案例分析），而不是 O(n+m).

您可以优化它以在 O(n+m) 时间内完成，方法是使用每次发生此操作时 initializes an array in O(1) 的算法。
这会将最坏情况下的时间复杂度从 O(n*m) 降低到 O(n+m)¹

_{(1)理论上，用同样的思路，甚至可以做到O(m)——不管计数器个数的大小，但是第一个allocation of the arrays takes O(n) time in java}

Answer 2

不要在遇到需要 O(N) 的 "max counter" 操作时调用 Arrays.fill(answer, minimumValue);，而应跟踪由于 [=17= 而分配的最后一个最大值] 操作，并在处理完所有操作后更新整个数组一次。这需要 O(N+M).

我将变量名称从 min 更改为 max 以减少混淆。

public class Solution {

    public int[] solution(int N, int[] A) {

        int highestCounter = N;
        int maxValue = 0;
        int lastMaxValue = 0;
        int [] answer = new int[N];

        for (int i = 0; i < A.length; i++) {
            int currentCounter = A[i]; 
            int answerEquivalent = currentCounter -1;

            if(currentCounter >0 && currentCounter<=highestCounter){
                if (answer[answerEquivalent] < lastMaxValue)
                    answer[answerEquivalent] = lastMaxValue +1;
                else 
                    answer[answerEquivalent] = answer[answerEquivalent]+1; 

                if(answer[answerEquivalent] > maxValue){
                    maxValue = answer[answerEquivalent];
                }
            }

            if (currentCounter == highestCounter +1){
                lastMaxValue = maxValue;
            }
        }
        // update all the counters smaller than lastMaxValue
        for (int i = 0; i < answer.length; i++) {
            if (answer[i] < lastMaxValue)
                answer[i] = lastMaxValue;
        }
        return answer;
    }

}

Answer 3

这有点像@Eran 的解决方案，但将功能封装在一个对象中。本质上 - 跟踪 max 值和 atLeast 值，让对象的功能完成其余的工作。

private static class MaxCounter {

    // Current set of values.
    final int[] a;
    // Keeps track of the current max value.
    int currentMax = 0;
    // Min value. If a[i] < atLeast the a[i] should appear as atLeast.
    int atLeast = 0;

    public MaxCounter(int n) {
        this.a = new int[n];
    }

    // Perform the defined op.
    public void op(int k) {
        // Values are one-based.
        k -= 1;
        if (k < a.length) {
            // Increment.
            inc(k);
        } else {
            // Set max
            max(k);
        }
    }

    // Increment.
    private void inc(int k) {
        // Get new value.
        int v = get(k) + 1;
        // Keep track of current  max.
        if (v > currentMax) {
            currentMax = v;
        }
        // Set new value.
        a[k] = v;
    }

    private int get(int k) {
        // Returns eithe a[k] or atLeast.
        int v = a[k];
        return v < atLeast ? atLeast : v;
    }

    private void max(int k) {
        // Record new max.
        atLeast = currentMax;
    }

    public int[] solution() {
        // Give them the solution.
        int[] solution = new int[a.length];
        for (int i = 0; i < a.length; i++) {
            solution[i] = get(i);
        }
        return solution;
    }

    @Override
    public String toString() {
        StringBuilder s = new StringBuilder("[");
        for (int i = 0; i < a.length; i++) {
            s.append(get(i));
            if (i < a.length - 1) {
                s.append(",");
            }
        }
        return s.append("]").toString();
    }
}

public void test() {
    System.out.println("Hello");
    int[] p = new int[]{3, 4, 4, 6, 1, 4, 4};
    MaxCounter mc = new MaxCounter(5);
    for (int i = 0; i < p.length; i++) {
        mc.op(p[i]);
        System.out.println(mc);
    }
    int[] mine = mc.solution();
    System.out.println("Solution = " + Arrays.toString(mine));
}

Answer 4

My solution: 1000

class Solution
    {
        public int maxCounterValue;

    public int[] Counters;

    public void Increase(int position)
    {
        position = position - 1;
        Counters[position]++;
        if (Counters[position] > maxCounterValue)
            maxCounterValue = Counters[position];
    }

    public void SetMaxCounter()
    {
        for (int i = 0; i < Counters.Length; i++)
        {
            Counters[i] = maxCounterValue;
        }
    }



    public int[] solution(int N, int[] A)
    {
        if (N < 1 || N > 100000) return null;
        if (A.Length < 1) return null;

        int nlusOne = N + 1;
        Counters = new int[N];
        int x;
        for (int i = 0; i < A.Length; i++)
        {
            x = A[i];
            if (x > 0 && x <= N)
            {
                Increase(x);
            }

            if (x == nlusOne && maxCounterValue > 0) // this used for all maxCounter values in array. Reduces addition loops
                SetMaxCounter();
            if (x > nlusOne)
                return null;
        }

        return Counters;

    }
}

Answer 5

( @molbdnilo : +1 !) 因为这只是一个算法测试，所以对变量说得太罗嗦是没有意义的。 "answerEquivalent" 用于 zero-based 数组索引调整？给我休息一下！只需回答 [A[i] - 1] 即可。
测试说假设 A 值总是介于 1 和 N+1 之间。所以不需要检查这个。
fillArray(.) 是一个 O(N) 过程，它在 O(M) 过程中。当所需的最大复杂度为 O(M+N) 时，这会使整个代码成为一个 O(M*N) 过程。实现此目的的唯一方法是仅结转计数器的当前最大值。这允许您在 A[i] 为 N+1 时始终保存正确的最大计数器值。后一个值是之后所有增量的一种基线值。在所有 A 值都被执行之后，那些从未通过数组条目递增的计数器然后可以通过复杂度 O(N) 的第二个 for 循环被提升到 all-counters 基线。

看看 Eran 的解决方案。

Answer 6

这就是我们可以消除 O(N*M) 复杂性的方法。
在此解决方案中，我尝试保留所有元素的最小值，而不是为每个 A[K]=N+1 填充结果数组，并在所有操作完成后更新结果数组。

如果有增加操作则更新那个位置:

  if (counter[x - 1] < minVal) {
     counter[x - 1] = minVal + 1;
  } else {
     counter[x - 1]++;
  }

并跟踪结果数组的每个元素的 minVal。

这里是完整的解决方案：

public int[] solution(int N, int[] A) {
    int minVal = -1;
    int maxCount = -1;

    int[] counter = new int[N];

    for (int i = 0; i < A.length; i++) {
        int x = A[i];

        if (x > 0 && x <= N) {
            if (counter[x - 1] < minVal) {
                counter[x - 1] = minVal + 1;

            } else {
                counter[x - 1]++;
            }

            if (maxCount < counter[x - 1]) {
                maxCount = counter[x - 1];
            }
        }

        if (x == N + 1 && maxCount > 0) {
            minVal = maxCount;
        }
    }

    for (int i = 0; i < counter.length; i++) {
        if (counter[i] < minVal) {
            counter[i] = minVal;
        }
    }

    return counter;
}

Answer 7

This is my swift 3 solution (100/100)

public func solution(_ N : Int, _ A : inout [Int]) -> [Int] {
  var counters = Array(repeating: 0, count: N)
  var _max = 0
  var _min = 0
  for i in A {
    if counters.count >= i {
      let temp = max(counters[i-1] + 1, _min + 1)
      _max = max(temp, _max)
      counters[i-1] = temp
    } else {
      _min = _max
    }
  }
  return counters.map { max([=10=], _min) }
}

我的代码的哪一部分使我的性能受到影响？（Codility 的 MaxCounter）

What part of my code is making my performance suffer? (Codility's MaxCounter)

java

algorithm

big-o

time-complexity

data-structures

我的代码的哪一部分使我的性能受到影响？ （Codility 的 MaxCounter）

What part of my code is making my performance suffer? (Codility's MaxCounter)

java

algorithm

big-o

time-complexity

data-structures

我的代码的哪一部分使我的性能受到影响？（Codility 的 MaxCounter）