我正在嘗試Codility使用給定的解決方案來解決的問題。該問題在下面提供: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] = 3A[1] = 4A[2] = 4A[3] = 6A[4] = 1A[5] = 4A[6] = 4the 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:class Solution { public int[] solution(int N, int[] A); }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.The sequence should be returned as:a structure Results (in C), ora vector of integers (in C++), ora record Results (in Pascal), oran array of integers (in any other programming language).For example, given: A[0] = 3 A[1] = 4 A[2] = 4 A[3] = 6 A[4] = 1 A[5] = 4 A[6] = 4the function should return [3, 2, 2, 4, 2], as explained above.Assume that: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].Complexity: expected worst-case time complexity is O(N+M); expected worst-case space complexity is O(N) (not counting the storage required for input arguments).看來他們使用2個存儲來保存和更新最小值/最大值,并在算法中使用它們。顯然,有一種更直接的方法可以解決該問題。將值增加1或?qū)⑺兄刀荚O(shè)置為建議的最大值,我可以做到這一點(diǎn)。缺點(diǎn)將是降低性能并增加時間復(fù)雜度。但是,我想了解這里的情況。我花了很多時間在示例數(shù)組上進(jìn)行調(diào)試,但是該算法仍然沒有什么令人困惑的地方。任何人都可以理解并可以向我簡要說明嗎?
查看完整描述