MaxCounters codility understanding

Question

나는 Codility에 대해 몇 가지 도전을하고 싶었고 처음부터 시작했다. 모든 과제는 MaxCounters에 비해 상대적으로 쉽습니다. 나는 고통스럽지 않은 것으로 표시된 첫 번째이지만이 사람이 특히 힘들다고 믿지 않습니다.

나는 task를 읽고 C# 언어로 코딩 시작 :

물론 3 개 루프를 갖는

public static int[] maxPart(int N, int[] A){ 
    int[] counters = new int[N]; 
    for(int i = 0; i < A.Length; i++){ 
     for(int j = 0; j < counters.Length; j++){ 
      if(A[i] == counters[j] && (counters[j] >= 1 && counters[j] <= N)){ 
       counters [j] = counters [j] + 1; 
      } 
      if(A[i] == N + 1){ 
       int tmpMax = counters.Max(); 
       for(int h = 0; h < counters.Length; h++){ 
        counters [h] = tmpMax; 
       } 
      } 
     } 
    } 
    return counters; 
} 

그것이 정말 느리게 만들지 만, 나중에두고 있습니다. 내 관심사는 내가 이걸 어떻게 이해했는지와 다른 모든 사람들이이 질문에 그것을 좋아하는 것입니다. here.

할당 설명에서.

는 2 개 동작 가지고

• 증가 (X) - 카운터 X를 1 증가
• 최대 카운터 - 모든 카운터는 임의 카운터의 최대 값으로 설정한다. 조건 발생

:

• 경우 예 A [K] = X, 즉 1 ≤ X ≤ N, 다음 동작 K가 증가이다 (X)
• 경우 [K] = N + 1이면 연산 K는 최대 카운터입니다.

두 조건 모두 위의 코드에 명시되어 있습니다. 불행히도 그것은 잘못되었지만 혼란 스럽습니다. 어떻게 다른지 이해할 수 있을지 모르겠습니다.

왜이 코드가 잘못 되었습니까? 작업 설명에 무엇이 누락 되었습니까? 최고 등급의 답변

하나는 다음과 같습니다 Codility에 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; 
} 

이 코드의 결과.

질문 :

나는 저자가 result[A[K] - 1]을 사용하는 작업에서 어떻게 알았는지 알고 싶습니다

? resetLimit은 무엇을 나타낼까요?

어쩌면 나는 나의 영어 때문에 질문을 완전히 오해했을 것입니다. 확실하지 않습니다. 나는 그냥 넘어갈 수 없다.

편집 : 내 코드를 기반으로

제공, 어떻게 할당을 잘못 이해 했습니까? 일반적으로 나는 문제의 설명을 요구하고있다. 수행해야 할 작업을 설명하거나 올바른 결과로 코드를 가져와 설명을 제공하고 이유를 이렇게 설명합니다.

Answer 1

필자는 여하튼 카운터의 인덱스 (A의 값)와 카운터의 값 (counter의 값)을 혼합했습니다. 그래서 A[i]-1을 사용할 때 마술은 없습니다. 문제 설명 (0부터 시작하는 인덱스로 조정)에서 값 X입니다.

내 순진 접근이 될 것이다, 나는 문제 (나는 그것을 명확하게 희망, 코드가 무슨 일을하고있다) 이해 방법 : 복잡 O(n^2) 같이 분명히

public static int[] maxPart(int N, int[] A){ 
    int[] counters = new int[N]; 
    for(int i = 0; i < A.Length; i++){ 
     int X=A[i]; 
     if(X>=1 && X<=N){ // this encodes increment(X), with X=A[i] 
      counters [X-1] = counters [X-1] + 1; //-1, because our index is 0-based 
     } 
     if(X == N + 1){// this encodes setting all counters to the max value 
      int tmpMax = counters.Max(); 
      for(int h = 0; h < counters.Length; h++){ 
        counters [h] = tmpMax; 
       } 
      } 
     } 
    } 
    return counters; 
} 

, 이것은 너무 느린 것을 다음 동작 시퀀스의 경우 조작 n=10^5 번호 (배열 A 길이)로 :

max counter, max counter, max counter, .... 

최고 등급의 용액을 지연하게하는 문제를 해결하고 명시 적으로 모든 값을 갱신하지 않는다 max counter 작업이 발생할 때마다이 카운터 값이 resetLimit에서 모든 카운터에 있어야하는 최소 값을 기억합니다. 따라서, 그는 카운터를 증가해야한다 때마다, 그는 그 값이 이전 max counter 작업으로 인해 업데이트해야하는지 여부를 조회하고 그가

if(result[A[K] - 1] < resetLimit) { 
       result[A[K] - 1] = resetLimit + 1; 
      } 

그의 솔루션에서 실행이 카운터에 실행되지 않은 모든 max counter 작동을 위해 구성하는 O(n)이며 충분히 빠릅니다.