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

我有以下问题：

你得到了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，返回表示计数器值的整数序列。

例如，给定：

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

函数应该返回[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).

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

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

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;
    }
}

我在这里的表现在哪里？该代码给出了正确的答案，但尽管具有适当的时间复杂性，但性能并没有达到规范要求。

您不应该在遇到"最大计数器"操作时调用Arrays.fill(answer, minimumValue);，该操作占用O(N)，而应该跟踪由于"最大计数"操作而分配的最后一个最大值，并在处理完所有操作后只更新整个数组一次。这需要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;
    }
}

以下操作为O(n)时间：

Arrays.fill(answer, minimumValue);

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

您可以优化它，使其在O(n+m)时间内完成，方法是每次执行此操作时使用在O(1)中初始化数组的算法。
这将把最坏情况下的时间复杂度从O(n*m)降低到O(n+m)¹

_{(1(理论上，使用相同的想法，它甚至可以在O(m)中完成-无论计数器数量的大小，但数组的第一次分配在java中需要O(n(时间}

这有点像@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));
}

我的解决方案：100\100

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;
    }
}

(@molbdnilo:+1！(因为这只是一个算法测试，所以对变量过于冗长是没有意义的。基于零的数组索引调整的"answerEquivalent"？让我休息一下！只要回答[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循环上升到所有计数器基线

看看Eran的解决方案。

这就是我们消除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;
}

这是我的swift 3解决方案(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($0, _min) }
}

相关内容

最新更新

热门标签：