MaxCounters

Calculate the values of counters after applying all alternating operations: increase counter by 1; set value of all counters to current maximum.

You are given N counters, initially set to 0, and you have two possible operations on them:

increase(X) − counter X is increased by 1, max counter − all counters are set to the maximum value of any counter. A non-empty array A of M integers is given. This array represents consecutive operations:

if A[K] = X, such that 1 ≤ X ≤ N, then operation K is increase(X), if A[K] = N + 1 then operation K is max counter. For example, given integer N = 5 and array A such that:

A[0] = 3
A[1] = 4
A[2] = 4
A[3] = 6
A[4] = 1
A[5] = 4
A[6] = 4

the values of the counters after each consecutive operation will be:

(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)

The goal is to calculate the value of every counter after all operations.

Write a function:

func Solution(N int, A []int) []int

that, given an integer N and a non-empty array A consisting of M integers, returns a sequence of integers representing the values of the counters.

Result array should be returned as an array of integers.

For example, given:

A[0] = 3
A[1] = 4
A[2] = 4
A[3] = 6
A[4] = 1
A[5] = 4
A[6] = 4

the function should return [3, 2, 2, 4, 2], as explained above.

Write an efficient algorithm for the following assumptions:

N and M are integers within the range [1..100,000]; each element of array A is an integer within the range [1..N + 1]. Copyright 2009–2021 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

題目大意

如果A[i] 小於 N 則將計數器中對應位置的數+1, 如果A[i] 大於 N 則將計數器中所有的數更新為計數器當前的最大數值

解題思路

來源

https://app.codility.com/programmers/lessons/4-counting_elements/

解答

https://github.com/kimi0230/LeetcodeGolang/blob/master/Codility/Lesson/0004.Counting-Elements/MaxCounters/MaxCounters.go

package MaxCounters

func Max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

// 時間 O(N+M) , 空間 O(N)
func Solution(N int, A []int) []int {
    result := make([]int, N)
    maxNum := 0
    nowMaxNum := 0
    for i := 0; i < len(A); i++ {
        if A[i] > N {
            // 如果A[i] 大於 N 則將計數器中所有的數更新為計數器當前的最大數值
            maxNum = nowMaxNum
        } else {
            // 如果A[i] 小於 N 則將計數器中對應位置的數+1,
            if result[A[i]-1] < maxNum {
                result[A[i]-1] = maxNum
            }
            result[A[i]-1]++

            if nowMaxNum < result[A[i]-1] {
                nowMaxNum = result[A[i]-1]
            }
        }
    }
    for i := 0; i < N; i++ {
        if result[i] < maxNum {
            result[i] = maxNum
        }
    }
    return result
}