gpt4 book ai didi

java codility 最大计数器

转载 作者:太空狗 更新时间:2023-10-29 22:31:11 26 4
gpt4 key购买 nike

我一直在努力解决以下任务:

你有 N 个计数器,初始设置为 0,你可以对它们进行两种可能的操作:

    increase(X) − counter X is increased by 1,
max_counter − all counters are set to the maximum value of any counter.

给出了一个由 M 个整数组成的非空零索引数组 A。这个数组代表连续的操作:

    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.

例如,给定整数 N = 5 和数组 A 使得:

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

每次连续操作后计数器的值将是:

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

目标是计算所有操作后每个计数器的值。

struct Results {
int * C;
int L;
};

写一个函数:

struct Results solution(int N, int A[], int M); 

给定一个整数 N 和一个由 M 个整数组成的非空零索引数组 A,返回表示计数器值的整数序列。

序列应返回为:

    a structure Results (in C), or
a vector of integers (in C++), or
a record Results (in Pascal), or
an array of integers (in any other programming language).

例如,给定:

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

函数应该返回 [3, 2, 2, 4, 2],如上所述。

假设:

    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].

复杂度:

    expected worst-case time complexity is O(N+M);
expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

可以修改输入数组的元素。

这是我的解决方案:

import java.util.Arrays;

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

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

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

if (localValue > currentMax) {
currentMax = localValue;
}
}

}

return countersArray;
}
}

这里是代码估值: https://codility.com/demo/results/demo6AKE5C-EJQ/

你能告诉我这个解决方案有什么问题吗?

最佳答案

问题出在这段代码上:

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)。我认为,一种解决此问题的方法是,在调用 max_counter 操作时,您可以将上次更新的值保留为变量,而不是显式更新整个数组 A。当调用第一个操作(递增)时,您只需查看您尝试递增的值是否大于 last_update。如果是,您只需将值更新为 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;
}
}

关于java codility 最大计数器,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19465965/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com