我试图解决这个算法问题:
https://dunjudge.me/analysis/problems/469/
为方便起见,我总结了下面的问题陈述.
给定包含[0,1,000,000]范围内的整数的长度(<= 2,000,000)数组,找到包含多数元素的最长子数组.
多数元素被定义为在长度为n的列表中发生> floor(n/2)次的元素.
时间限制:1.5秒
例如:
如果给定的数组是[1,2,1,2,3,2],
答案是5,因为从位置1到5(0索引)的长度为5的子阵列[2,1,2,3,2]具有数字2,其显示3> floor(5/2)次.请注意,我们不能采用整个数组,因为3 = floor(6/2).
首先想到的是一个明显的暴力(但正确)解决方案,它解决了子阵列的起始和结束索引并循环遍历它以检查它是否包含多数元素.然后我们采用包含多数元素的最长子阵列的长度.这在O(n ^ 2)中工作,具有小的优化.显然,这不会超过时限.
我还想把元素分成包含排序顺序的索引的桶.
使用上面的示例,这些桶将是:
1:0,2
2:1,3,5
3:4
然后对于每个桶,我会尝试将索引合并在一起以找到包含k作为多数元素的最长子阵列,其中k是该桶的整数标签.然后我们可以在k的所有值上取最大长度.我没有尝试这个解决方案,因为我不知道如何执行合并步骤.
编辑:
由于PhamTrung和hk6279的答案,我解决了这个问题.虽然我接受了PhamTrung的答案,因为他首先提出了这个想法,但我强烈建议你看一下hk6279的答案,因为他的回答详细阐述了PhamTrung的想法并且更详细(并且还附带了一个很好的正式证据!).
注意:尝试1是错误的,因为@ hk6279给出了一个反例.谢谢你指出来.
尝试1: 答案非常复杂,所以我将讨论一个简短的想法
让我们逐个处理每个唯一的号码.
x在索引处从左到右处理每个出现的数字i,让我们添加一个段(i, i)表示当前子数组的开始和结束.在那之后,我们需要查看该段的左侧,并尝试将该段的左邻居合并到(i, i)(因此,如果左边是(st, ed),(st, i)如果可能的话,我们会尝试使其变为满足条件),如果可能的话,并继续合并它们直到我们无法合并,或者没有左邻居.
我们将所有这些段保留在堆栈中,以便更快地查找/添加/删除.
最后,对于每个细分,我们尝试尽可能大地扩大它们,并保持最大的结果.
时间复杂度应该是O(n)每个元素只能合并一次.
尝试2:
让我们逐个处理每个唯一的号码
对于每个唯一的数字x,我们维护一个计数器阵列.从0到数组的末尾,如果我们遇到一个值,x我们增加计数,如果我们不减少,那么对于这个数组[0,1,2,0,0,3,4,5,0, 0]和数字0,我们有这个数组计数器
[1,0,-1,0,1,0,-1,-2,-1,0]
因此,为了使有效的子数组以特定索引结束i,其值counter[i] - counter[start - 1]必须大于0(如果您将数组视为从1和-1条目生成,则可以很容易地解释这一点;有1 is when there is an occurrence of x, -1 otherwise;并且问题可以被转换为找到子数并且总和是积极的)
因此,在二分搜索的帮助下,上述算法仍然具有O(n ^ 2 log n)的复杂度(如果我们有n/2个唯一数字,我们需要进行上述过程n/2次,每次时间取O(n log n))
为了改进它,我们做了一个观察,我们实际上不需要存储所有计数器的所有值,而只是计数器的值x,我们看到我们可以存储上面的数组计数器:
[1,#,#,0,1,#,#,#, - 1,0]
这将导致O(n log n)解决方案,该解决方案仅通过每个元素一次.