我刚刚完成了以下Codility Peaks问题.问题如下:
给出了由N个整数组成的非空零索引数组A. 峰值是一个比其邻居更大的数组元素.更确切地说,它是指数P,使得0 <P <N-1,A [P-1] <A [P]和A [P]> A [P + 1].例如,以下数组A:
A[0] = 1
A[1] = 2
A[2] = 3
A[3] = 4
A[4] = 3
A[5] = 4
A[6] = 1
A[7] = 2
A[8] = 3
A[9] = 4
A[10] = 6
A[11] = 2
有三个峰:3,5,10.我们想把这个数组分成包含相同数量元素的块.更确切地说,我们想要选择一个能产生以下块的数字K:A [0],A [1],...,A [K-1],A [K],A [K + 1], ...,A [2K - 1],... A [N - K],A [N - K + 1],...,A [N - 1].更重要的是,每个块应包含至少一个峰值.请注意,块的极端元素(例如A [K-1]或A [K])也可以是峰值,但前提是它们同时具有两个邻居(包括相邻块中的一个).目标是找到阵列A可以划分的最大块数.数组A可以分为以下块:
一个街区(1,2,3,4,3,4,1,2,3,4,6,2).该块包含三个峰.
两个块(1,2,3,4,3,4)和(1,2,3,4,6,2).每个街区都有一个高峰.
三个块(1,2,3,4),(3,4,1,2),(3,4,6,2).每个街区都有一个高峰.
特别注意第一个块(1,2,3,4)在A [3]处有一个峰值,因为A [2] <A [3]> A [4],即使A [4]在相邻的街区.但是,阵列A不能分为四个块,(1,2,3),(4,3,4),(1,2,3)和(4,6,2),因为(1,2, 3)块不包含峰值.特别注意(4,3,4)块包含两个峰:A [3]和A [5].阵列A可以分成的最大块数是三个.
编写函数:class Solution {public int solution(int [] A); 在给定由N个整数组成的非空零索引数组A的情况下,返回A可以划分的最大块数.如果A不能分成若干个块,则该函数应返回0.例如,给定:
A[0] = 1
A[1] = 2
A[2] = 3
A[3] = 4
A[4] = 3
A[5] = 4
A[6] = 1
A[7] = 2
A[8] = 3
A[9] = 4
A[10] = 6
A[11] = 2
该函数应返回3,如上所述.假使,假设:
N是[1..100,000]范围内的整数; 数组A的每个元素是[0..1,000,000,000]范围内的整数.
复杂:
预期的最坏情况时间复杂度为O(N*log(log(N)))
预期的最坏情况空间复杂度是O(N),超出输入存储(不计入输入参数所需的存储).
可以修改输入数组的元素.
所以我解决了这个问题,对我来说似乎是一个强力解决方案 - 遍历每个组的大小1..N,并检查每个组是否至少有一个峰值.在我尝试解决这个问题的前15分钟,我试图找出一些更优化的方法,因为所需的复杂度是O(N*log(log(N))).
这是我的"暴力"代码,它通过所有测试,包括大型测试,得分为100/100:
public int solution(int[] A) {
int N = A.length;
ArrayList<Integer> peaks = new ArrayList<Integer>();
for(int i = 1; i < N-1; i++){
if(A[i] > A[i-1] && A[i] > A[i+1]) peaks.add(i);
}
for(int size = 1; size <= N; size++){
if(N % size != 0) continue;
int find = 0;
int groups = N/size;
boolean ok = true;
for(int peakIdx : peaks){
if(peakIdx/size > find){
ok = false;
break;
}
if(peakIdx/size == find) find++;
}
if(find != groups) ok = false;
if(ok) return groups;
}
return 0;
}
我的问题是我如何推断这实际上是O(N*log(log(N))),因为它对我来说并不是很明显,我对通过测试用例感到惊讶.我正在寻找最简单的复杂性证明草图,这将使我相信这个运行时.我假设log(log(N))因子意味着在每次迭代时通过平方根来减少问题,但我不知道这是如何适用于我的问题的.非常感谢您的帮助
你完全正确:要获得日志日志性能,需要减少问题.
python [下面]中的n.log(log(n))解决方案.Codility不再测试此问题的"性能"(!),但python解决方案的准确性得分为100%.
正如你已经推测的那样: 外部循环将是O(n),因为它正在测试每个块的大小是否是一个干净的除数 内部循环必须是O(log(log(n)))才能得到O(n log(log) (n)))总体而言.
我们可以获得良好的内循环性能,因为我们只需要执行d(n),即n的除数.我们可以存储peak-so-far的前缀和,它使用问题规范允许的O(n)空间.然后检查每个'组'中是否发生峰值是使用组开始和结束索引的O(1)查找操作.
遵循该逻辑,当候选块大小为3时,循环需要执行n/3个峰值检查.复杂度变为总和:n/a + n/b + ... + n/n,其中分母(a,b,...)是n的因子.
简短说明: nd(n)操作的复杂性是O(n.log(log(n))).
更长的版本: 如果您已经完成了Codility课程,您将从第8课:Prime和复合数字中记住,谐波数运算的总和将给出O(log(n))复杂度.我们有一个减少的集合,因为我们只关注因子分母.第9课:Eratosthenes的筛子显示了素数的倒数之和是O(log(log(n)))并声称"证明是非平凡的".在这种情况下,维基百科告诉我们,除数sigma(n)的总和有一个上限(参见Robin的不等式,大约是页面的一半).
这完全回答了你的问题吗？关于如何改进我的python代码的建议也非常受欢迎!
def solution(data):
length = len(data)
# array ends can't be peaks, len < 3 must return 0
if len < 3:
return 0
peaks = [0] * length
# compute a list of 'peaks to the left' in O(n) time
for index in range(2, length):
peaks[index] = peaks[index - 1]
# check if there was a peak to the left, add it to the count
if data[index - 1] > data[index - 2] and data[index - 1] > data[index]:
peaks[index] += 1
# candidate is the block size we're going to test
for candidate in range(3, length + 1):
# skip if not a factor
if length % candidate != 0:
continue
# test at each point n / block
valid = True
index = candidate
while index != length:
# if no peak in this block, break
if peaks[index] == peaks[index - candidate]:
valid = False
break
index += candidate
# one additional check since peaks[length] is outside of array
if index == length and peaks[index - 1] == peaks[index - candidate]:
valid = False
if valid:
return length / candidate
return 0
致谢: @tmyklebu对他的回答非常感谢,这对我帮助很大.
我不认为你的算法的时间复杂度是O(Nlog(logN))。
然而，它肯定比 O(N^2) 小得多。这是因为您的内部循环仅输入 k 次，其中 k 是 N 的因子数。整数的因子数可以在此链接中查看：http://www.cut-the-knot.org/blue /因子数.shtml
我可能不准确，但从链接看来，
k ~ logN * logN * logN ...
此外，内部循环的复杂度为 O(N)，因为在最坏的情况下峰值数量可能为 N/2。
因此，在我看来，算法的复杂度最多为 O(NlogN) ，但它必须足以清除所有测试用例。