14

次の問題があります。

最初は 0 に設定された N 個のカウンターが与えられ、それらに対して 2 つの操作が可能です。

  • 増加（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)

目標は、すべての操作の後にすべてのカウンターの値を計算することです。

私は次の解決策を実行しましたが、K = 配列 A の長さである O(NK) で実行されます。

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

K が配列 A の長さである場合、O(N + K) を使用してこれをより適切に行う方法を誰かに教えてもらえますか? ひどいコーディングで申し訳ありませんが、プログラミングを改善するためにこれらの演習を行っています。ありがとう！

4

22 に答える 22

17

これは私が思いついたものですが、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;
}
于 2013-09-20T04:34:50.260 に答える
6

覚えて：

「コードを読みやすくすることは、実行可能にすることと同じくらい重要です。」

-- ロバート・C・マーティン

難しい問題を解こうとしても…

そのため、読みやすさを向上させるために、カウンター配列とその操作をカプセル化するクラスを作成しました ( Demeter の法則)。悲しいことに、私の最初のソリューションはパフォーマンス テストで 60% しか得られなかったので、読みやすさを少し犠牲にして、よりスマートなソリューションで改善し、最終的に 100% を得ました。

コメント付きの2つの実装を次に示します。

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カプセル化の美しさに注意してください。アルゴリズムを改善するには、メソッドの文字を 1 つも変更せずに、クラスのいくつかのメソッドを編集するだけ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();
    }
}

誠実さの結果

于 2016-07-02T04:11:25.573 に答える
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
于 2013-11-11T12:07:36.533 に答える
2

これが私が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
于 2014-02-02T01:17:14.243 に答える
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)。配列を再初期化する順序をカウントする方法によって異なります。

于 2013-09-20T04:56:14.710 に答える
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();
    }
}
于 2015-06-28T17:09:46.093 に答える
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;
}
于 2020-10-31T23:34:04.383 に答える
1

迅速な解決策 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
}
于 2020-04-19T09:54:29.740 に答える
0

これは 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/

于 2015-10-26T17:06:15.450 に答える
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
于 2016-02-08T07:17:59.370 に答える
0

重要なのは、[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
于 2015-09-09T12:44:15.290 に答える
0

C++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;
}
于 2015-07-23T05:06:25.673 に答える
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
于 2018-10-29T05:14:49.653 に答える