如何在kotlin中增加可变列表的大小限制

Question

我试图解决multiset问题(https://codeforces.com/contest/1354/problem/D)关于使用Fenwick Tree数据结构的代码部队。我通过了示例测试用例，但在提交后出现了内存限制错误，下面提到了测试用例。(基本上测试用例是：

1000000

1…………..1//10^6次

-1…………..-1//10^6次(。

我在IDE中尝试了类似的测试用例，得到了下面提到的错误。(与上面类似，我提供的测试用例是：

1000000 1

1…………..1//10^6次

-1

)

线程中的异常"；主"；java.lang.IndexOutOfBoundsException：索引524289超出长度524289的界限位于java.base/jdk.internal.util.Prequisitions.outOfBounds(Preconditions.java:64(位于java.base/jdk.internal.util.Prequisitions.outOfBoundsCheckIndex(Preconditions.java:70(位于java.base/jdk.internal.util.Prequisitions.checkIndex(Preconditions.java:248(位于java.base/java.util.Objects.checkIndex(Objects.java:373(位于java.base/java.util.ArrayList.get(ArrayList.java:426(在MultisetKt.main(MultisetKt:47(在MultisetKt.main(multiset.kt(

这是我的代码：

private fun readInt() = readLine()!!.split(" ").map { it.toInt() }
fun main() {
var (n, q) = readInt()
var list = readInt() //modify the list to store it from index 1
var finalList = listOf(0) + list
val query = readInt()
var bit  = MutableList(n+1){0}
fun update(i:Int, value:Int) {
var index = i
while(index < n){
bit.set (index , bit[index] + value)
index += (index and -index)
}
}
fun rangefunc(i:Int): Int {
var su = 0
var index = i
while(index > 0){
su += bit[index]
index -= (index and -index)
}
return su
}
fun find(x:Int):Int {
var l = 1
var r = n
var ans = n
var mid = 0
while (l <= r) {
mid = (l + r) / 2
if (rangefunc(mid) >= x) {
ans = mid
r = mid - 1
} else {
l = mid + 1
}
}
return ans
}
for (i in 1..n) {
update(finalList[i], 1)
}
for (j in 0..q - 1) {
if (query[j] > 0) {
update(query[j], 1)
} else {
update(find(-query[j]), -1)
}
}
if(rangefunc(n) == 0){
println(0)
}else{
println(find(1))
}
}

我相信这是因为BITlist不能存储10^6元素，但不能确定。请让我知道我应该对代码进行哪些更改，以及关于未来如何处理此类情况的任何其他建议。

提前感谢：(

Answer 1

一个ArrayList可以存储超过20亿个项目(2*10^9(。这不是你的问题。ArrayIndexOutOfBoundsException用于尝试访问小于零或大于等于其大小的ArrayList的索引。换句话说，它还没有包含的索引。

那里的代码比我调试的时间还多。但是，我将从堆栈跟踪所指向的行开始，看看如何使用等于ArrayList大小的索引来尝试调用bit[index]。

为了回答您的字面问题，您可以显式使用LinkedList作为您的MutableList类型，以避免大小限制，但通过索引访问元素时，它更重，速度也更慢。