Массовые счетчики java

Ответ 1

Проблема связана с этим фрагментом кода:

for (int iii = 0; iii < A.length; iii++) {
     ...
     if (currentValue == condition) {
         Arrays.fill(countersArray, currentMax);
     }
     ...
}

Представьте, что каждый элемент массива A был инициализирован значением N+1. Поскольку вызов функции Arrays.fill(countersArray, currentMax) имеет временную сложность O(N), тогда общий алгоритм будет иметь временную сложность O(M * N). Как я могу исправить это, вместо явного обновления всего массива A, когда вызывается операция max_counter, вы можете сохранить значение последнего обновления как переменной. Когда вызывается первая операция (приращение), вы просто видите, превышает ли значение, которое вы пытаетесь увеличить, <<28 > . Если вы просто обновите значение с помощью 1, в противном случае вы инициализируете его до last_update + 1. Когда вызывается вторая операция, вы просто обновляете last_update до current_max. И, наконец, когда вы закончите и попытаетесь вернуть окончательные значения, вы снова сравниваете каждое значение с last_update. Если это больше, вы просто сохраняете значение, иначе вы возвращаете last_update

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

        final int condition = N + 1;
        int currentMax = 0;
        int lastUpdate = 0;
        int countersArray[] = new int[N];

        for (int iii = 0; iii < A.length; iii++) {
            int currentValue = A[iii];
            if (currentValue == condition) {
                lastUpdate = currentMax
            } else {
                int position = currentValue - 1;
                if (countersArray[position] < lastUpdate)
                    countersArray[position] = lastUpdate + 1;
                else
                    countersArray[position]++;

                if (countersArray[position] > currentMax) {
                    currentMax = countersArray[position];
                }
            }

        }

        for (int iii = 0; iii < N; iii++)
           if (countersArray[iii] < lastUpdate)
               countersArray[iii] = lastUpdate;

        return countersArray;
    }
}

Ответ 2

Проблема в том, что когда вы получаете множество операций max_counter, вы получаете много вызовов Arrays.fill, что замедляет ваше решение.

Вы должны сохранить currentMax и currentMin:

• Когда вы получаете max_counter, вы просто устанавливаете currentMin = currentMax.
• Если вы получите другое значение, позвоните ему i:
  • Если значение в позиции i - 1 меньше или равно currentMin, вы устанавливаете его на currentMin + 1.
  • В противном случае вы увеличиваете его.

В конце просто перейдите в массив счетчиков и установите все меньше currentMin в currentMin.

Ответ 3

Еще одно решение, которое я разработал и, возможно, стоит рассмотреть: http://codility.com/demo/results/demoM658NU-DYR/

Ответ 4

Это 100% -ное решение этого вопроса.

// you can also use imports, for example:
// import java.math.*;
class Solution {
    public int[] solution(int N, int[] A) {
        int counter[] = new int[N];
        int n = A.length;
        int max=-1,current_min=0;

        for(int i=0;i<n;i++){
            if(A[i]>=1 && A[i]<= N){
                if(counter[A[i] - 1] < current_min) counter[A[i] - 1] = current_min;
                counter[A[i] - 1] = counter[A[i] - 1] + 1;
                if(counter[A[i] - 1] > max) max = counter[A[i] - 1];
            }
            else if(A[i] == N+1){
                current_min = max;
            }
        }
        for(int i=0;i<N;i++){
            if(counter[i] < current_min) counter[i] =  current_min;
        }
        return counter;
    }
}

Ответ 5

Вот мое решение на С++, которое получило 100 на кодовости. Концепция такая же, как описано выше.

int maxx=0;
int lastvalue=0;
void set(vector<int>& A, int N,int X)
    {
        for ( int i=0;i<N;i++)
            if(A[i]<lastvalue)
                A[i]=lastvalue;
    }

vector<int> solution(int N, vector<int> &A) {
    // write your code in C++11

    vector<int> B(N,0);
    for(unsigned int i=0;i<A.size();i++)
        {
            if(A[i]==N+1)
               lastvalue=maxx;

            else
            {   if(B[A[i]-1]<lastvalue)
                    B[A[i]-1]=lastvalue+1;
                else
                    B[A[i]-1]++;
                if(B[A[i]-1]>maxx)
                    maxx=B[A[i]-1];
            }

        }
        set(B,N,maxx);
    return B;
}

Ответ 6

vector<int> solution(int N, vector<int> &A)
{
    std::vector<int> counters(N);
    auto max = 0;
    auto current = 0;

    for (auto& counter : A)
    {
        if (counter >= 1 && counter <= N)
        {
            if (counters[counter-1] < max)
                counters[counter - 1] = max;

            counters[counter - 1] += 1;

            if (counters[counter - 1] > current)
                current = counters[counter - 1];
        }
        else if (counter > N)
            max = current;

    }

    for (auto&& counter : counters)
        if (counter < max)
            counter = max;

    return counters;
}

Ответ 7

  vector<int> solution(int N, vector<int> &A) 
{
    std::vector<int> counter(N, 0); 
    int max = 0;
    int floor = 0;

    for(std::vector<int>::iterator i = A.begin();i != A.end(); i++)
    {
        int index = *i-1;
        if(*i<=N && *i >= 1)
        {
            if(counter[index] < floor)
              counter[index] = floor;
            counter[index] += 1;
            max = std::max(counter[index], max);
        }
        else
        {
            floor = std::max(max, floor);
        }
    }
    for(std::vector<int>::iterator i = counter.begin();i != counter.end(); i++)
    {
       if(*i < floor)
         *i = floor;
    }
    return counter;
}

Ответ 8

Hera - это мое решение AC Java. Идея такая же, как и @Inwvr:

public int[] solution(int N, int[] A) {
        int[] count = new int[N];
        int max = 0;
        int lastUpdate = 0;
        for(int i = 0; i < A.length; i++){
            if(A[i] <= N){
                if(count[A[i]-1] < lastUpdate){
                    count[A[i]-1] = lastUpdate+1;   
                }
                else{
                    count[A[i]-1]++;
                }    
                max = Math.max(max, count[A[i]-1]);
            }
            else{
                lastUpdate = max;   
            }
        }  
        for(int i = 0; i < N; i++){
            if(count[i] < lastUpdate)
                count[i] = lastUpdate;
        }    
        return count;
    }

Ответ 9

Я добавляю другое решение Java 100 с некоторыми тестовыми примерами, в которых они полезны.

// https://codility.com/demo/results/demoD8J6M5-K3T/ 77
// https://codility.com/demo/results/demoSEJHZS-ZPR/ 100
public class MaxCounters {

  // Some testcases
  // (1,[1,2,3]) = [1]
  // (1,[1]) = [1]
  // (1,[5]) = [0]
  // (1,[1,1,1,2,3]) = 3
  // (2,[1,1,1,2,3,1]) = [4,3]
  // (5, [3, 4, 4, 5, 1, 4, 4]) = (1, 0, 1, 4, 1)
  public int[] solution(int N, int[] A) {
      int length = A.length, maxOfCounter = 0, lastUpdate = 0;
      int applyMax = N + 1;
      int result[] = new int[N];

      for (int i = 0; i < length; ++i ) {
          if(A[i] == applyMax){
              lastUpdate = maxOfCounter;
          } else if (A[i] <= N)  {
              int position = A[i]-1;
              result[position] = result[position] > lastUpdate
                                        ? result[position] + 1 : lastUpdate + 1;
              // updating the max for future use
              if(maxOfCounter <=  result[position]) {
                  maxOfCounter = result[position];
              }
          }
     }
     // updating all the values that are less than the lastUpdate to the max value
     for (int i = 0; i < N; ++i) {
         if(result[i] < lastUpdate) {
             result[i] = lastUpdate;
         }
     }
     return result;
   }
}

Ответ 10

Я только что получил 100 на PHP с некоторой помощью из вышеперечисленного

function solution($N, $A) {
    $B = array(0);
    $max = 0;

    foreach($A as $key => $a) {
        $a -= 1;
        if($a == $N) {
            $max = max($B);
        } else {
            if(!isset($B[$a])) {
                $B[$a] = 0;
            }

            if($B[$a] < $max) {
                $B[$a] = $max + 1;
            } else {
                $B[$a] ++;
            }

        }

    }

    for($i=0; $i<$N; $i++) {
        if(!isset($B[$i]) || $B[$i] < $max) {
            $B[$i] = $max;
        }

    }

    return $B;


}

Ответ 11

Это еще одно решение для С++.

Обоснование всегда одно и то же.

• Избегайте устанавливать максимальный счетчик счетчика на второй, поскольку это приведет к сложности O (N * M).
• Подождите, пока мы не получим другой код операции на одном счетчике.
• В этот момент алгоритм запоминает, выполнил ли он max_counter и, следовательно, установил значение счетчика.

Здесь код:

vector<int> MaxCounters(int N, vector<int> &A) 
{
    vector<int> n(N, 0);
    int globalMax = 0;
    int localMax = 0;

    for( vector<int>::const_iterator it = A.begin(); it != A.end(); ++it)
    {
        if ( *it >= 1 && *it <= N)
        {
            // this is an increase op.
            int value = *it - 1;
            n[value] = std::max(n[value], localMax ) + 1;
            globalMax = std::max(n[value], globalMax);
        }
        else
        {
            // set max counter op.
            localMax = globalMax;
        }
    }

    for( vector<int>::iterator it = n.begin(); it != n.end(); ++it)
        *it = std::max( *it, localMax );

    return n;
}

Ответ 12

100%, O (m + n)

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

    int[] counters = new int[N];
    int maxAIs = 0;
    int minAShouldBe = 0;

    for(int x : A) {
        if(x >= 1 && x <= N) {
            if(counters[x-1] < minAShouldBe) {
                counters[x-1] = minAShouldBe;
            }

            counters[x-1]++;

            if(counters[x-1] > maxAIs) {
                maxAIs = counters[x-1];
            }
        } else if(x == N+1) {
            minAShouldBe = maxAIs;
        }
    }

    for(int i = 0; i < N; i++) {
        if(counters[i] < minAShouldBe) {
            counters[i] = minAShouldBe;
        }
    }

    return counters;
}

Ответ 13

вот мой код, но его 88% причина занимает 3,80 секунды для 10000 элементов вместо 2.20

класс Решение {

boolean maxCalled;

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

int max =0;
int [] counters = new int [N];
    int temp=0;
    int currentVal = 0;
    for(int i=0;i<A.length;i++){
    currentVal = A[i];
    if(currentVal <=N){
        temp = increas(counters,currentVal);
        if(temp > max){
        max = temp;
        }
    }else{
        if(!maxCalled)
        maxCounter(counters,max);
    }

    }

    return counters;

}


int increas (int [] A, int x){  
 maxCalled = false;
 return ++A[x-1];  
 //return t;
}

void maxCounter (int [] A, int x){
 maxCalled = true;
  for (int i = 0; i < A.length; i++) {
 A[i] = x;
  }

}

}

Ответ 14

Arrays.fill() вызов внутри массива interation делает программу O (N ^ 2)

Здесь - это возможное решение, которое имеет время выполнения O (M + N).

Идея -

• Для второй операции отслеживайте максимальное значение, которое достигается посредством приращения, это наше базовое значение до текущей итерации, никакие значения не могут быть меньше этого.

• Для первой операции сбросьте значение до базового значения, если необходимо до приращения.

  public static int [] solution (int N, int [] A) {   int counters [] = new int [N];

  int base = 0;
  int cMax = 0;
  
  for (int a : A) {
      if (a > counters.length) {
          base = cMax;
      } else {
          if (counters[a - 1] < base) {
              counters[a - 1] = base;
          }
  
          counters[a - 1]++;
  
          cMax = Math.max(cMax, counters[a - 1]);
      }
  }
  
  for (int i = 0; i < counters.length; i++) {
      if (counters[i] < base) {
          counters[i] = base;
      }
  }
  
  return counters;
  

  }

Ответ 15

Следуя моему решению в JAVA (100/100).

public boolean isToSum(int value, int N) {
    return value >= 1 && value <= N;
}

public int[] solution(int N, int[] A) {
    int[] res = new int[N];
    int max =0;
    int minValue = 0;

    for (int i=0; i < A.length; i++){
        int value = A[i];
        int pos = value -1;
        if ( isToSum(value, N)) {
            if( res[pos] < minValue) {
                res[pos] = minValue;
            }
            res[pos] += 1;
            if (max < res[pos]) {
                max = res[pos];
            }
        } else {
            minValue = max;
        }
    }

    for (int i=0; i < res.length; i++){
        if ( res[i] < minValue ){
            res[i] = minValue;
        }
    }
    return res;
}

Ответ 16

мое решение:

public class Solution {  

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

            int[] counters = new int[N];
            int[] countersLastMaxIndexes = new int[N];
            int maxValue = 0;
            int fixedMaxValue = 0;
            int maxIndex = 0;
            for (int i = 0; i < A.length; i++) {
                if (A[i] <= N) {
                    if (countersLastMaxIndexes[A[i] - 1] != maxIndex) {
                        counters[A[i] - 1] = fixedMaxValue;
                        countersLastMaxIndexes[A[i] - 1] = maxIndex;

                    }
                    counters[A[i] - 1]++;
                    if (counters[A[i] - 1] > maxValue) {
                        maxValue = counters[A[i] - 1];
                    }
                } else {
                    maxIndex = i;
                    fixedMaxValue = maxValue;
                }

            }
            for (int i = 0; i < countersLastMaxIndexes.length; i++) {
                if (countersLastMaxIndexes[i] != maxIndex) {
                    counters[i] = fixedMaxValue;
                    countersLastMaxIndexes[i] = maxIndex;
                }
            }

            return counters;
        }
}

Ответ 17

В моем Java-решении я обновлял значения в Solution [] только при необходимости. И наконец обновленное решение [] с правильными значениями.

public int[] solution(int N, int[] A) {
    int[] solution = new int[N];
    int maxCounter = 0;
    int maxCountersSum = 0;
    for(int a: A) {
        if(a >= 1 && a <= N) {
            if(solution[a - 1] < maxCountersSum)
                solution[a - 1] = maxCountersSum;
            solution[a - 1]++;
            if(solution[a - 1] > maxCounter)
                maxCounter = solution[a - 1];
        }
        if(a == N + 1) {
            maxCountersSum = maxCounter;
        }
    }
    for(int i = 0; i < N; i++) {
        if(solution[i] < maxCountersSum)
            solution[i] = maxCountersSum;
    }

    return solution;
}

Ответ 18

Вот мое решение Python:

def solution(N, A):
    # write your code in Python 3.6
    RESP = [0] * N
    MAX_OPERATION = N + 1
    current_max = 0
    current_min = 0
    for operation in A:
        if operation != MAX_OPERATION:
            if RESP[operation-1] <= current_min:
                RESP[operation-1] = current_min + 1
            else:
                RESP[operation-1] += 1

            if RESP[operation-1] > current_max:
                current_max = RESP[operation-1]
        else:
            if current_min == current_max:
                current_min += 1
            else:
                current_min = current_max

    for i, val in enumerate(RESP):
        if val < current_min:
            RESP[i] = current_min
    return RESP

Ответ 19

def sample_method(A,N=5):
    initial_array = [0,0,0,0,0]
for i in A:

    if(i>=1):
      if(i<=N):
        initial_array[i-1]+=1
      else:
        for a in range(len(initial_array)):
          initial_array[a]+=1
    print i
    print initial_array

Ответ 20

Здесь мое решение с использованием Python 3.6. Результат - 100% правильность, но 40% производительность (большинство из них были из-за тайм-аута). До сих пор не могу понять, как оптимизировать этот код, но, надеюсь, кто-то найдет его полезным.

def solution(N, A):
    count = [0]*(N+1)
    for i in range(0,len(A)):
        if A[i] >=1 and A[i] <= N:
            count[A[i]] += 1
        elif A[i] == (N+1): 
            count = [max(count)] * len(count)
    count.pop(0)
    return count

Ответ 21

Машинопись:

function counters(numCounters: number, operations: number[]) {
const counters = Array(numCounters)

let max = 0
let currentMin = 0

for (const operation of operations) {
    if (operation === numCounters + 1) {
        currentMin = max
    } else {
        if (!counters[operation - 1] || counters[operation - 1] < currentMin) {
            counters[operation - 1] = currentMin
        }

        counters[operation - 1] = counters[operation - 1] + 1

        if (counters[operation - 1] > max) {
            max += 1
        }
    }
}

for (let i = 0; i < numCounters; i++) {
    if (!counters[i] || counters[i] < currentMin) {
        counters[i] = currentMin
    }
}

return counters

}

console.log(solution=${counters(5, [3, 4, 4, 6, 1, 4, 4])})

Ответ 22

Решение JavaScript на 100 пунктов, включает в себя улучшение производительности, чтобы игнорировать повторяющиеся итерации max_counter:

function solution(N, A) {
    let max = 0;
    let counters = Array(N).fill(max);
    let maxCounter = 0;

    for (let op of A) {
        if (op <= N && op >= 1) {
            maxCounter = 0;
            if (++counters[op - 1] > max) {
                max = counters[op - 1];
            }
        } else if(op === N + 1 && maxCounter === 0) {
            maxCounter = 1;
            for (let i = 0; i < counters.length; i++) {
                counters[i] = max;   
            }
        }
    }

    return counters;
}

Ответ 23

решение в JAVA (100/100)

    class Solution {
    public int[] solution(int N, int[] A) {
        // write your code in Java SE 8
        int[] result = new int[N];
        int base = 0;
        int max = 0;
        int needToChange=A.length;;
        for (int k = 0; k < A.length; k++) {
            int X = A[k];
            if (X >= 1 && X <= N) {

                if (result[X - 1] < base) {
                    result[X - 1] = base;
                }
                result[X - 1]++;
                if (max < result[X - 1]) {
                    max = result[X - 1];
                }
            }
            if (X == N + 1) {
                base = max;
                needToChange= X-1;

            }
        }
        for (int i = 0; i < needToChange; i++) {
            if (result[i] < base) {
                result[i] = base;
            }
        }
        return result;

    }

}