Алгоритм: Макс. Счетчики

У меня есть следующая проблема:

Вам предоставляется 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