算法：最大计数器

我有以下问题：

你有N个计数器，最初设置为0，你有两个可能的操作：

• 增加（X） – 计数器X增加1，
• max_counter – 所有计数器都设置为任何计数器的最大值。

给出了M个整数的非空零索引数组A. 此数组表示连续操作：

• 如果A [K] = X，使得1≤X≤N，则操作K增加（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 =arraysA的长度。

 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]  N + 1) throw new InvalidOperationException(); if (A[K] >= 1 && A[K]  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的长度？ 很抱歉可能编码很糟糕，我正在做这些练习来改进我的编程。 谢谢！

Answer 1

这就是我提出的，但我不确定它是否100％有效：

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

Answer 2

 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 

Answer 3

这是我在Python中提出的解决方案（100/100关于codility）; 它与我在这里看到的其他人有点不同，所以我想分享：

 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 

Answer 4

记得：

“使代码可读是与使其可执行一样重要。”

– 罗伯特C马丁

即使在试图解决一个难题时……

因此，为了实现更好的可读性，我创建了一个类来封装计数器数组及其操作（ Demeter法则 ）。 可悲的是，我的第一个解决方案只有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结果

Answer 5

让我们来看看…

 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) 。 取决于您如何计算重新初始化arrays的顺序。

Answer 6

与每个人真正得分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(); } } 

Answer 7

 public int[] counters(int N, int[] A) { int[] count = new int[N]; int maxCount = 0; int setAll = 0; for (int i = 0; i < A.Length; i++) { if (A[i] == N + 1) { setAll += maxCount; maxCount = 0; count = new int[N]; } else { count[A[i] - 1] += 1; if (count[A[i] - 1] > maxCount) { maxCount = count[A[i] - 1]; } } } for (int j = 0; j < count.Length; j++) { count[j] += setAll; } return count; } 

我认为这是O（N + K），但是可靠性说它的O（N * K）？ 如果有人能解释哪个是正确的，将不胜感激......

Answer 8

php中的100/100解决方案

 function solution($N, $A){ $cond = $N + 1; $cur_max = 0; $last_upd = 0; $cnt_arr = array(); $cnt = count($A); for($i = 0; $i < $cnt; $i++){ $cur = $A[$i]; if($cur == $cond){ $last_upd = $cur_max; } else{ $pos = $cur - 1; if(!isset($cnt_arr[$pos])){ $cnt_arr[$pos] = 0; } if($cnt_arr[$pos] < $last_upd){ $cnt_arr[$pos] = $last_upd + 1; } else{ $cnt_arr[$pos] ++; } if($cnt_arr[$pos] > $cur_max){ $cur_max = $cnt_arr[$pos]; } } } for($i = 0; $i < $N; $i++){ if(!isset($cnt_arr[$i])){ $cnt_arr[$i] = 0; } if($cnt_arr[$i] < $last_upd){ $cnt_arr[$i] = $last_upd; } } return $cnt_arr; } 

Answer 9

Rue，我刚刚在当地运行。 自己看了看柜台。 我用这个算法：

  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 { resetlimit = maximum; result = Enumerable.Repeat(maximum, result.Length).ToArray(); } } //for (int i = 0; i < result.Length; i++) //{ // result[i] = Math.Max(resetlimit, result[i]); //} return result; } } 

查看问题和结果集，您必须在else语句中包含低效的for循环。 外部的for循环不会复制第二个操作
•如果A [K] = N + 1，则操作K为max_counter。

为了迭代A [3] = 6将result [] all设置为'2'，必须使用最大计数器加载结果数组。 否则，您的返回将永远不会有（2,2,2,2,2），如第四个示例数组所示。

我也必须通过考试来完成我梦寐以求的工作，因此这里效率低下很重要;

该声明

  result = Enumerable.Repeat(maximum, result.Length).ToArray(); 

一次性加载数组所以没有内循环，没有内部效率。 我认为这非常接近正确的结果集。 我很惊讶他们没有要求像总回报的锯齿状arrays那样回归。 尽管如此，这种痘痘测试让我很害怕。

Answer 10

C ++ 11代码：

 #include  vector solution(int N, vector &A) { vector hist(N, 0); int last_update = 0; int max_value = 0; for (auto i : A){ if (1 <= i && i <= N){ int& val = hist[i - 1]; if (val < last_update) val = last_update + 1; else val++; if (max_value < val) max_value = val; } if (i == (N+1)){ last_update = max_value; } } replace_if(hist.begin(), hist.end(), [last_update](int x){return x < last_update;}, last_update); return hist; } 

Answer 11

关键是[0] * N是N操作。 如果它存在于for循环中，它将变为N * M. 在Codility中测试100％

  # you can write to stdout for debugging purposes, eg # print "this is a debug message" def solution(N, A): # write your code in Python 2.7 count = [0] * N maxCounter = 0 minCounter = 0 for x in A: if x <= N and x >= 1: count[x-1] = max(count[x-1], minCounter) + 1 if maxCounter < count[x-1]: maxCounter = count[x-1] if x == N + 1: minCounter = maxCounter for i in xrange(N): count[i] = max(count[i], minValue) return count 

Answer 12

这是Scala版本，100％关于codility：

 import java.util def solution(N: Int, A: Array[Int]): Array[Int] = { var counters = new Array[Int](N) var maxCounter = 0 for(ind <- 0 to A.length-1){ if(A(ind) == (N+1)){ //all to max util.Arrays.fill(counters,maxCounter) }else{ //ind -1 cause array index start with 0 which is marked as 1 in the input data counters(A(ind)-1) += 1 //update max counter if necessary if(maxCounter< (counters(A(ind)-1))) maxCounter = (counters(A(ind)-1)) } } return counters } 

表现： https ： //codility.com/demo/results/trainingKJT6Y3-74G/

Answer 13

获得100/100的Ruby Codility Code

 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 

Answer 14

 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