|
|
这个题目第一次做得到90分，大大提高了信心。
给定一个非空的从零起始的数组A，包含N个整数。(P, Q) 满足 0<=P<=Q<N, 被称作A的一个slice。(P, Q) 的sum表示 A[P]+A[P+1]+...+A[Q].
min abs slice 表示一个slice，其sum的绝对值是最小的。
举例来说，数组A
A[0] = 2 A[1] = -4 A[2] = 6 A[3] = -3 A[4] = 9
包含以下slice（不仅这些）- (0, 1), whose absolute sum = |2 + (4)| = 2
- (0, 2), whose absolute sum = |2 + (4) + 6| = 4
- (0, 3), whose absolute sum = |2 + (4) + 6 + (3)| = 1
- (1, 3), whose absolute sum = |(4) + 6 + (3)| = 1
- (1, 4), whose absolute sum = |(4) + 6 + (3) + 9| = 8
- (4, 4), whose absolute sum = |9| = 9
slices (0, 3) 和 (1, 3) 都是min abs slice, 他们的绝对值和等于1.
算法要求如下：
给定非空，索引从0开始的数组A，包含N个整数，寻求 min abs slice，返回其sum的绝对值。
假定：- N的取值范围为[1..100,000];
- A中元素取值范围为[10,000..10,000].
复杂度要求：- 时间复杂度为 O(N*log(N));
- 空间复杂度为 O(N)
原文如下：
A non-empty zero-indexed array A of N integers is given. A pair of integers (P, Q), such that 0 ≤ P ≤ Q < N, is called a slice of array A. The sum of a slice (P, Q) is the total of A[P] + A[P+1] + ... + A[Q].
A min abs slice is a slice whose absolute sum is minimal.
For example, array A such that:
<tt> A[0] = 2 A[1] = -4 A[2] = 6 A[3] = -3 A[4] = 9</tt>
contains the following slices, among others:- (0, 1), whose absolute sum = |2 + (4)| = 2
- (0, 2), whose absolute sum = |2 + (4) + 6| = 4
- (0, 3), whose absolute sum = |2 + (4) + 6 + (3)| = 1
- (1, 3), whose absolute sum = |(4) + 6 + (3)| = 1
- (1, 4), whose absolute sum = |(4) + 6 + (3) + 9| = 8
- (4, 4), whose absolute sum = |9| = 9
Both slices (0, 3) and (1, 3) are min abs slices and their absolute sum equals 1.
Write a function: <tt>class Solution { public int solution(int[] A); }</tt> that, given a non-empty zero-indexed array A consisting of N integers, returns the absolute sum of min abs slice.
For example, given:
<tt> A[0] = 2 A[1] = -4 A[2] = 6 A[3] = -3 A[4] = 9</tt>
the function should return 1, as explained above.
Assume that:- N is an integer within the range [1..100,000];
- each element of array A is an integer within the range [10,000..10,000].
Complexity:- expected worst-case time complexity is O(N*log(N));
- expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).
Elements of input arrays can be modified.
实现：
public int solution(int[] A) {
int sum = 0;
int n = A.length;
int[] sums = new int[n];
for (int i=0; i<n; i++) {
sum += A[i];
if (sum == 0) return 0;
sums[i] = sum;
}
// 问题转换为数组sums[], 寻找两个元素之差的绝对值最小 min(|S[P] - S[Q]|), 即点之间的最小距离
Arrays.sort(sums);
int ans = Math.abs(sums[0]);
for (int i=0; i<n-1; i++) {
ans = Math.min(ans, Math.abs(sums[i+1] - sums[i]));
}
return ans;
} |
----------------------------
原文链接:https://blog.51cto.com/fushan/1673955
程序猿的技术大观园：www.javathinker.net
[这个贴子最后由 flybird 在 2020-03-15 19:13:11 重新编辑]
|
|
Java技术网站 → 『 Java开发技术 』 → 『 数据结构和算法专题 』 → Codility 算法测验
消息
查看
搜索
好友
邮件
复制
引用
IP: 已设置保密
