Andrea Giuliano
10/14/2020, 8:31 AMfirst.intersect(second.toList()).toIntArray()
but this is not really O(n). It takes more time than just using standard comparison one by one (using the property that the 2 IntArrays are ordered). I wonder if there is something elegant to solve this in Kotlin? An ugly way to do this fast would be with something like
private fun intersection(a: IntArray, b: IntArray): IntArray {
val c = IntArray(min(a.size, b.size))
if (c.isEmpty()) {
return c
}
var i = 0
var j = 0
var k = 0
while (i < a.size && j < b.size) {
val aa = a[i]
val bb = b[j]
val comparison = aa - bb
if (comparison == 0) {
c[k++] = aa
i++
j++
} else if (comparison < 0) {
i++
} else {
j++
}
}
return c.copyOf(k)
}
nanodeath
10/14/2020, 4:34 PMAndrea Giuliano
10/14/2020, 4:37 PMnanodeath
10/14/2020, 4:38 PM(data: IntArray, size: Int) -> Unit
as a third argument and pass c, k
directly to that. though admittedly that'd look a little weird.aa.compareTo(bb)
aa < bb
directlyephemient
10/14/2020, 8:21 PMmin()
is not in kotlin stdlib, minOf()
is-
for comparison, it can overflow and give the wrong result, e.g.
Int.MIN_VALUE - Int.MAX_VALUE > 0
nanodeath
10/14/2020, 8:23 PMcompareTo
ftwephemient
10/14/2020, 8:38 PMIntArray
for performance then I'm not sure there's much else you can donanodeath
10/14/2020, 8:45 PMephemient
10/14/2020, 9:37 PMAndrea Giuliano
10/16/2020, 9:32 AM