计算巨大/大数组中的不同元素的数量

好的,这个解决方案不是内存效率,但它将用于计算O(1)中的查询.

形成另一个7000x10的2D数组,其中每一行都是该条目的[0到9s]的计数.

因此,无论何时获得查询,您只需要减去行的相应索引以获得[0..9]数的计数.

检查哪些指数具有非零计数差异.

例如,数组行可能如下所示:

A[36] = { 5, 4, 2,  1, 4, 3, 7, 8, 2, 1 }
A[38] = { 6, 4, 2,  1, 4, 3, 7, 8, 2, 2 }

Diff =  { 1, 0, 0,  0, 0, 0, 0, 0, 0, 1 }

所以在36和38之间有两个独特的元素(0和9).

示例2:
对于输入数组{1,2,3,2,4},矩阵A应为:

A[0] = { 0, 1, 0,  0, 0, 0, 0, 0, 0, 0 }
A[1] = { 0, 1, 1,  0, 0, 0, 0, 0, 0, 0 }
A[2] = { 0, 1, 1,  1, 0, 0, 0, 0, 0, 0 }
A[3] = { 0, 1, 2,  1, 0, 0, 0, 0, 0, 0 }
A[4] = { 0, 1, 2,  1, 1, 0, 0, 0, 0, 0 }

所以对于A [3]到A [4],应该有1个唯一元素(4)

Diff =  { 0, 0, 0,  0, 1, 0, 0, 0, 0, 0 }

所以对于A [1]到A [4],应该有3个唯一元素(2,3,4)

Diff =  { 0, 0, 1,  1, 1, 0, 0, 0, 0, 0 }

编辑:我已经考虑过A [1]到A [4]的含义是指数[2到4]中的唯一元素.如果需要,可以将其更改为1到4.在这种情况下,

Diff =  { 0, 0, 2,  1, 1, 0, 0, 0, 0, 0 }

(再次3个独特的元素)