Алгоритм: Макс. Счетчики
У меня есть следующая проблема:
Вам предоставляется N счетчиков, изначально заданных в 0, и у вас есть две возможные операции над ними:
- увеличение (X) - счетчик X увеличивается на 1,
- max_counter - все счетчики установлены на максимальное значение любого счетчика.
Дается непустой нуль-индексированный массив A из целых чисел M. Этот массив представляет собой последовательные операции:
- если 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 = длина массива 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? Извините за ужасное кодирование, я делаю эти упражнения, чтобы улучшить свое программирование. Спасибо!
Ответы
Ответ 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;
}
Ответ 2
Помните:
"Сделать ваш код читаемым так же важно, как сделать его исполняемым".
- Роберт С Мартин
Даже при попытке решить сложную проблему...
Поэтому, пытаясь добиться лучшей читаемости, я создал класс для инкапсуляции массива счетчиков и его операций (Закон Деметры). К сожалению, мое первое решение получило всего 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();
}
}
Результат кодиментации
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();
}
}
Результат кодиментации
Ответ 3
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
Ответ 4
Вот решение, которое я придумал в Python (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
Ответ 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). Зависит от того, как вы рассчитываете порядок повторной инициализации массива.
Ответ 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();
}
}
Ответ 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)? Был бы признателен, если бы кто-нибудь мог объяснить, что правильно...
Ответ 8
Решение 100/100 в php
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;
}
Ответ 9
Рю, Я просто это сделал локально. Смотрел сам счетчики. Я использовал этот алгоритм:
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 снаружи не реплицирует вторую операцию
• если A [K] = N + 1, то операция K является max_counter.
Чтобы итерация A [3] = 6, чтобы установить результат [] все в '2', вы должны загрузить массив результатов с максимальным счетчиком. В противном случае ваше возвращение никогда не будет (2,2,2,2,2), как показывает 4-й пример массива.
Я тоже должен пройти тест, чтобы получить работу моей мечты, поэтому здесь важна небольшая неэффективность;
утверждение
result = Enumerable.Repeat(maximum, result.Length).ToArray();
загружает массив всего за один выстрел, поэтому нет внутреннего цикла и внутреннего эффекта. Я думаю, что это довольно близко к правильным наборам результатов. Я удивлен, что они не просили вернуться, как зубчатый массив полного возвращения. Тем не менее, этот тест на кодовость меня пугает.
Ответ 10
Код С++ 11:
#include <algorithm>
vector<int> solution(int N, vector<int> &A) {
vector<int> 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;
}
Ответ 11
Ключ состоит в том, что [0] * N - операция N. Если это существует в цикле for, оно станет N * M. Испытано в Codility 100%
# you can write to stdout for debugging purposes, e.g.
# 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
Ответ 12
Вот версия Scala, 100% на доступность:
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/
Ответ 13
Код кодировки Ruby, который получил 100/100
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
Ответ 14
Рубин 100%
def solution(n, a)
max = 0
offsets = a.inject(Hash.new(max)) do |acc, el|
next Hash.new(max) if el == n+1
acc[el] +=1
max = acc[el] if max < acc[el]
acc
end
(1..n).map{|i| offsets[i]}
end
Ответ 15
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
