logo标签列表

算法：最大计数器

c#algorithmpuzzle
15

我有以下问题：

给定N个计数器，初始值为0，你可以对它们执行两种操作：

  • increase(X) − 将计数器X加1。
  • max_counter − 将所有计数器设置为所有计数器中的最大值。

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

  • 如果A[K] = X（其中1≤X≤N），则操作K是increase(X)；
  • 如果A[K] = N + 1，则操作K是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)

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

我尝试了以下解决方案，但它的运行时间为 O(NK)，其中 K 是数组 A 的长度。

public int[] solution(int N, int[] A) {
    int[] result = new int[N];
    int maximum = 0;

    for (int K = 0; K < A.Length; K++)
    {
        if (A[K] < 1 || A[K] > N + 1)
            throw new InvalidOperationException();

        if (A[K] >= 1 && A[K] <= N)
        {
            result[A[K] - 1]++;

            if (result[A[K] - 1] > maximum)
            {
                maximum = result[A[K] - 1];
            }
        }
        else
        {
            // inefficiency here
            for (int i = 0; i < result.Length; i++)
                result[i] = maximum;
        }
    }

    return result;
}

有人能展示一下如何用O(N + K)的时间复杂度来更好地完成这个任务吗？这里的K是数组A的长度。很抱歉我的代码很糟糕，我正在做这些练习来提高我的编程水平。谢谢！

我对复杂度分析并不是很了解，但你的代码/算法看起来像是O(N)——因为你只遍历一次'A'数组，而且如果所有计数器有时都要达到最大值，你选择的for循环似乎足够高效。 - גלעד ברקן
我在Codility上尝试了这个问题，只得了71分。我知道有比我的更好的解决方案。 - Randal Cunanan
1
这不是O(n)，因为当将所有内容都设置为最大值时，O(n)并且假设每个调用都是设置最大值，则O(n)*O(n)=O(N^2)。顺便说一句，代码是错误的，因为最大值在运行时更新，并且它不是全局最大值。 - Sinn
什么是全局最大值？我需要在运行时更新最大值，以免引入另一个循环来检查最大值。此外，代码通过了多个输入数据，唯一的问题是处理大型数组时的性能。 - Randal Cunanan
嗯，我把你的代码转换成了JavaScript，并在Codility上得了66分...哈哈，看来这并不像看起来那么简单。 - גלעד ברקן
显示剩余2条评论
22个回答
17

这是我想出来的，但我不确定它是否百分之百可行：

public int[] solution(int N, int[] A) {
    int[] result = new int[N];
    int maximum = 0;
    int resetLimit = 0;

    for (int K = 0; K < A.Length; K++)
    {
        if (A[K] < 1 || A[K] > N + 1)
            throw new InvalidOperationException();

        if (A[K] >= 1 && A[K] <= N)
        {
            if (result[A[K] - 1] < resetLimit) {
                result[A[K] - 1] = resetLimit + 1;
            } else {
                result[A[K] - 1]++;
            }

            if (result[A[K] - 1] > maximum)
            {
                maximum = result[A[K] - 1];
            }
        }
        else
        {
            // inefficiency here
            //for (int i = 0; i < result.Length; i++)
            //    result[i] = maximum;
            resetLimit = maximum;
        }
    }

    for (int i = 0; i < result.Length; i++)
        result[i] = Math.Max(resetLimit, result[i]);

    return result;
}
1
恭喜！我在 Codility 上测试了你的调整，得分为100%。 - גלעד ברקן
1
谢谢！因为你们，我正在学习新的编程技巧。 - Randal Cunanan
6

记住：

"让你的代码易读与可执行同等重要。"

-- 罗伯特·马丁

即使在解决难题时...

为了更好的可读性，我创建了一个封装计数器数组及其操作的类（迪米特法则）。不幸的是，我的第一个解决方案只有60%的性能测试结果，因此为了稍微牺牲一点可读性，我用更聪明的方法改进了它，最终获得了100%的性能表现。

这里是我两个实现的代码，带有注释：

O(N*M)正确性100% / 性能60%（高可读性）

//I didn't refactored the names of the variables N and A
//to maintain it aligned with the question description
public int[] solution(int N, int[] A)
{
    var counters = new Counters(N);

    for (int k = 0; k < A.Length; k++)
    {
        if (A[k] <= N)
            counters.IncreaseCounter(A[k]);
        else
            counters.MaxAllCounters();
    }

    return counters.ToArray();
}

public class Counters
{
    private int[] counters;
    private int greaterValueInCounter = 0;

    public Counters(int length)
    {
        counters = new int[length];
    }

    public void MaxAllCounters()
    {
        for (int i = 0; i < counters.Length; i++)
        {
            counters[i] = greaterValueInCounter;
        }
    }

    public void IncreaseCounter(int counterPosition)
    {
        //The counter is one-based, but our array is zero-based
        counterPosition--;

        //Increments the counter
        counters[counterPosition]++;

        if (counters[counterPosition] > greaterValueInCounter)
            greaterValueInCounter = counters[counterPosition];
    }

    //The counters array is encapsuled in this class so if we provide external 
    //acess to it anyone could modify it and break the purpose of the encapsulation
    //So we just exposes a copy of it :)
    public int[] ToArray()
    {
        return (int[])counters.Clone();
    }
}

Codility结果

O(N+M) 正确性100% / 性能100%（可读性不太高）

注意封装的美：要改进算法，我只需编辑Counters类的一些方法，而无需在solution方法上更改任何字符。

Counters类中编辑的方法：

  • IncreaseCounter()
  • MaxAllCounters()
  • ToArray()

最终代码：

//Exactly the same code
public int[] solution(int N, int[] A)
{
    var counters = new Counters(N);

    for (int k = 0; k < A.Length; k++)
    {
        if (A[k] <= N)
            counters.IncreaseCounter(A[k]);
        else
            counters.MaxAllCounters();
    }

    return counters.ToArray();
}

public class Counters
{
    private int[] counters;
    private int greaterValueInCounter = 0;
    private int currentEquilibratedScore = 0;

    public Counters(int length)
    {
        counters = new int[length];
    }

    public void MaxAllCounters()
    {
        //We don't update the entire array anymore - that was what caused the O(N*M)
        //We just save the current equilibrated score value
        currentEquilibratedScore = greaterValueInCounter;
    }

    public void IncreaseCounter(int counterPosition)
    {
        //The counter is one-based, but our array is zero-based
        counterPosition--;

        //We need to add this "if" here because with this new solution the array
        //is not always updated, so if we detect that this position is lower than
        //the currentEquilibratedScore, we update it before any operation
        if (counters[counterPosition] < currentEquilibratedScore)
            counters[counterPosition] = currentEquilibratedScore + 1;
        else
            counters[counterPosition]++;

        if (counters[counterPosition] > greaterValueInCounter)
            greaterValueInCounter = counters[counterPosition];
    }

    //The counters array is encapsuled in this class so if we provide external 
    //acess to it anyone could modify it and break the purpose of the encapsulation
    //So we just exposes a copy of it :)
    public int[] ToArray()
    {
        //Now we need to fix the unupdated values in the array
        //(the values that are less than the equilibrated score)
        for (int i = 0; i < counters.Length; i++)
        {
            if (counters[i] < currentEquilibratedScore)
                counters[i] = currentEquilibratedScore;
        }

        return (int[])counters.Clone();
    }
}

Codility result

4
def solution(N, A):
    # write your code in Python 2.6
    res = [0] * N
    m = 0
    minValue = 0
    for x in A:
        if 1 <= x <= N:
            res[x - 1] = max(res[x - 1], minValue) + 1
            if res[x - 1] > m:
                m = res[x - 1]
        else:
            minValue = m
    for i in xrange(N):
        res[i] = max(res[i], minValue)
    return res
2

这是我在Python中想出的解决方案（在codility上得分为100/100）；它与我在这里看到的其他解决方案有点不同，所以我想分享一下：

def solution(N, A):
    count = [0] * N
    max_counter = [i for i, a in enumerate(A) if a == N+1]
    if len(max_counter) == len(A):
        return count
    if max_counter:
        mode = 0
        for i, m in enumerate(max_counter):
            if m == 0 or m - max_counter[i-1] == 1:
                continue
            subcount = {}
            if i == 0:
                for k in A[:m]:
                    if k not in subcount:
                        subcount[k] = 1
                    else:
                        subcount[k] += 1
            else:
                for k in A[max_counter[i-1]+1:m]:
                    if k not in subcount:
                        subcount[k] = 1
                    else:
                        subcount[k] += 1
            mode += max(subcount.values())
        count = [mode] * N
        for k in A[max_counter[-1]+1:]:
            count[k-1] += 1
    else:
        for k in A:
            count[k-1] += 1
    return count
1

和每个人都得到100%的原理相同，只是我发现这个版本更容易阅读（可能仅因为我写了它）。

using System;
using System.Linq;

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

        var currentMax = 0;
        var resetValue = 0;
        var counters = Enumerable.Range(1, N).ToDictionary(i => i, i => 0);

        foreach (var a in A)
        {
            if (a == N + 1) resetValue = currentMax;
            else
            {
                counters[a] = Math.Max(counters[a], resetValue) + 1;
                currentMax = Math.Max(currentMax, counters[a]);
            }
        }
        return counters.Values.Select(v => Math.Max(v,resetValue)).ToArray();
    }
}
1

让我们看看...

public int[] Solution(int N, int[] A)
{
    int[] data = new int[N];
    int maxval = 0;
    int baseval = 0;
    for (int K = 0; K < A.length; K++)
    {
        int index = A[K] - 1;
        if (index < 0 || index > N)
            throw new InvalidOperationException();

        if (index < N)
            maxval = baseval + Math.Max(maxval, ++data[index]);
        else
        {
            baseval = maxval;
            data = new int[N];
        }
    }

    for (int K = 0; K < N; K++)
        data[K] += baseval;

    return data;
}

我认为这是O(N+K)。取决于你如何计算重新初始化数组的顺序。
1
这是一个在PHP中的实现：

function solution($N, $A) {
    $output = array_fill(0, $N, 0);
    $maxCounter = 0;
    $minCounter = 0;
    foreach ($A as $number) {
        if($number === $N + 1) {
            $minCounter = $maxCounter;
        } else if($number <= $N) {
            $number--;
            if($minCounter > $output[$number]) {
                $output[$number] = $minCounter;
            }
            $output[$number]++;
            if($output[$number] > $maxCounter) $maxCounter = $output[$number];
        }
    }

    foreach ($output as $index => $number) {
        if($number < $minCounter) $output[$index] = $minCounter;
    }

//    var_dump($output);
    return $output;
}
1

Swift 解决方案 100％

public func solution(_ N : Int, _ A : inout [Int]) -> [Int] {
    // write your code in Swift 4.2.1 (Linux)

    var solution = Array.init(repeating: 0, count: N)

        var max = 0
        var actualMaxValue = 0

        for obj in A {

            if (obj <= N && obj >= 1 ) {

                if solution[obj-1] < actualMaxValue {

                    solution [obj-1] = actualMaxValue + 1
                } else {

                    solution[obj-1] += 1
                }

                if (solution[obj-1] > max) {

                    max = solution[obj-1]
                }
            }
            else if obj == N+1 {

              actualMaxValue = max
            }
        }

    for (index, value) in solution.enumerated() {


        if value < actualMaxValue {

            solution[index] = actualMaxValue
        }
    }


    return solution
}
1
请不要仅仅发布代码作为答案，还要提供解释您的代码是如何解决问题的。带有解释的答案通常质量更高，更有可能吸引赞同。 - David Buck
0

得分100/100的Ruby Codility代码

def solution(a)

  if a.length < 3
      0
  end
  a.sort!
  for i in 2..a.length - 1
    if (a[i-2] + a[i-1]) > a[i]
      return 1
    end
  end
 0
end
0
def solution(N, A):
    res = [0] * N
    maxV, minV = 0, 0
    for x in A:
        if 1 <= x <= N:
            res[x-1] = max(res[x-1], minV) + 1
            maxV = max(maxV, res[x-1])
        else: minV = maxV
    for i in range(N):
        res[i] = max(res[i], minV)
    return res
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接