[GO] [100%] MaxCounters (src & junit & author's note)
Respectable
MaxCounters
After applying all the alternating operations, calculate the value of the counter. Increase the counter by one. Sets the values of all counters to the current maximum.
Task description
Initially given N counters set to 0, there are two possible operations on them.
Increase (X)-Counter X is incremented by 1. max counter-All counters are set to the maximum value of any counter. Given a non-empty array A of M integers. This array represents a series of operations.
- If A [K] = X and 1 ≤ X ≤ N, then the operation K is increase (X),
- If A [K] = N + 1, operation K is the maximum counter.
For example, suppose the integer N = 5 and the array A looks like this:
A [0] = 3
A [1] = 4
A [2] = 4
A [3] = 6
A [4] = 1
A [5] = 4
A [6] = 4
The value of the counter after each consecutive operation is as follows.
（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 values of all counters after every operation.
Write a function:
class solution {public int [] solution（int N、int [] A）; }
Given a non-empty array A of integers N and M, it returns a sequence of integers representing the values of the counter.
The resulting array should be returned as an array of integers.
For example:
A [0] = 3
A [1] = 4
A [2] = 4
A [3] = 6
A [4] = 1
A [5] = 4
A [6] = 4
As explained above, the function should return [3, 2, 2, 4, 2].
Write an efficient algorithm for the following assumptions:
- N and M are integers in the range [1..100,000].
- Each element of array A is an integer in the range [1..N + 1].
solve
Author's note
The key to this problem is that all members of the array must be assigned the current maximum element value when MaxCounter occurs. If you have a large number of array members, assigning a value to each member or assigning a value frequently can be quite computationally expensive. This is called a ** "storm" ** in situations where the internet is highly concurrent, even network storms, cash storms, avalanches, etc. If a storm or frequent storms occur, it is catastrophic to the system. There are many reasons for a "storm" and the corresponding measures are different. The key to this issue is to consider how to deal with the "all-element allocation" problem and whether it can maintain high performance even with frequent "all-element allocation".
Author Roc Yang Equipment Note: This problematic relationship: At the time of Develop Max Counter, the largest element in the past, the large number of existing groups, the valuation, the valuation, the valuation, the valuation, the valuation, and the merits. Under the scene of the high-level concurrency of the Internet, usually named ** "cache" **, cache network, cache, avalanche, etc. A disaster or a disaster, a disaster or a disaster. "Absurdity" productive causes There are many, and there is no difference between them. The subject matter is solved, and the problem is "all-in-one", and the problem is "all-in-one".
Program MaxCountersSolution.java
Author Rockyan Note: The solution used here: This issue requires that all array elements be assigned to the current maximum element value when MaxCounter occurs (thus, a storm can occur). Temporarily write down the current maximum element value when MaxCounter occurs, and then add the element's MaxCounter operation (that is, assign the maximum and +1) the next time the element performs a +1 operation. If so, no storm will occur. Note: The +1 operation does not occur on all elements, so you need to make sure that all elements are filled with MaxCounter operations. (This method is often used in internet applications. For example, in an SNS scenario, a large V posts an article. If a user who subscribes to a large V article immediately pushes the content of the article, a storm occurs. There is likely to be. The storm is effectively avoided by pulling articles that the client subscribes to only when the client logs in. Of course, in real-world social media scenarios, there are other complex services to consider, such as sending notifications to subscribed users, so we won't cover them here. Interested friends, welcome to leave a message and discuss together. )
Author Roc Yang Equipment Note: How to solve this problem: At the time of the development of the subject request MaxCounter, the number of elements possessed by the valuation is the largest element before the time of development (physiologically possible production). Young, at the time of development of this MaxCounter, the maximum element before valuation, and at the time of the next certain element +1 operation, the elemental MaxCounter operation (immediate valuation maximum, parallel +1) The meeting is over. Note: Inevitable individual element Urban development +1 operation, possession most important element 检 查 Yes / No possession element Metropolitan MaxCounter operation. . At the time of registration of the young client, the client's client's abduction self-reliant text, Masaru Najo's effective evasion and violent development. Naturally, in the genuine SNS scene, existence and other recovery business, notification of user transmission, etc., on the scene demand consideration, absence of this exhibition. A hobbyist friend, a sneak peek. )
MaxCountersSolution.java
public int[] solution(int N, int[] A) {
int[] B = new int[N];
int currentMaximumValue = 0;
int minValue = 0;
for (int i = 0; i < A.length; i++) {
if (A[i] == N + 1) {
if (minValue < currentMaximumValue) {
minValue = currentMaximumValue;
}
} else {
if (B[A[i] - 1] < minValue) {
B[A[i] - 1] = minValue;
}
B[A[i] - 1] += 1;
if (B[A[i] - 1] > currentMaximumValue) currentMaximumValue = B[A[i] - 1];
}
}
for (int j = 0; j < B.length; j++) {
B[j] = B[j] < minValue ? minValue : B[j];
}
return B;
}
jUnit MaxCountersSolutionTest.java
Report Candidate Report: training9KQG2K-34P
Detected time complexity:
O(N + M)
Recommended Posts