在大小为n*k + b的数组中找到b次发生的元素

Question

描述

给定一个大小数组,(n*k+b)其中n个元素出现k次,一个元素出现b次,换句话说,有n+1不同的元素.鉴于0 < b < k找到b次元素.

我的尝试解决方案

1. 显而易见的解决方案是使用散列,但如果数字非常大,则不起作用.复杂性是O(n)

2. 使用map存储每个元素的频率,然后遍历map以找到b次出现的元素.由于Map的实现为高度平衡树,复杂性将是O(nlogn).

我的两个解决方案都被接受了,但是面试官想要一个线性解决方案,而不使用散列和暗示他给出的树的高度在你存储频率的树中保持不变,但我还没有找到正确的解决方案.

我想知道如何在没有散列的线性时间内解决这个问题？

编辑:

样品:

输入: n=2 b=2 k=3

Aarray: 2 2 2 3 3 3 1 1

输出: 1

Answer 1

我假设:

1. 阵列的元素是可比较的.
2. 我们事先知道n和k的值.
3. 解O(n*k + b)就足够了.

设数只出现b次.我们试图在n*k + b大小的数组中找到S.

递归步骤:找到当前数组切片的中间元素,如同在生产线时间中快速排序一样.设中位元素为M.

在递归步骤之后,你有一个数组,其中所有小于M的元素出现在M的第一个出现的左边.所有M个元素彼此相邻,所有大于M的元素都在M的所有出现的右边.

查看最左边的M的索引并计算S <M或S> = M. 递归在左切片或右切片上.

因此,您正在进行快速排序,但在任何时候只钻研部门的一部分.您将递归O(logN)次,但每次都使用原始阵列的1/2,1/4,1/8,...尺寸,因此总时间仍为O(n).

澄清:假设n = 20且k = 10.然后,阵列中有21个不同的元素,其中20个出现10次,最后一次出现让我们说7次.我找到了中等元素,假设它是1111.如果S <1111比最左边出现的1111的指数小于11*10.如果S> = 1111则索引将等于11*10.

完整示例: n = 4. k = 3.数组= {1,2,3,4,5,1,2,3,4,5,1,2,3,5}在第一个递归步骤后,我找到了中间元素是3,数组类似于:{1,2,1,2,1,2,3,3,3,5,4,5,5,4}左边有6个元素. 6是k = 3的倍数.所以每个元素必须在那里发生3次.所以S> = 3.递归右侧.等等.

Answer 2

使用循环组的想法.

要猜测第i位答案,请按照以下步骤操作:

1. 计算数组中第i位设置的数量,存储为 cnt
2. 如果cnt % k不为零,则设置第i位答案.否则很清楚.

要猜测整数,请对每一位重复上述操作.

这个解决方案在技术上O((n*k+b)*log max N),max N表中的最大值,但由于位数通常是常数,因此该解决方案在数组大小上是线性的.

没有散​​列,内存使用是O(log k * log max N).

示例实现:

from random import randint, shuffle

def generate_test_data(n, k, b):
    k_rep = [randint(0, 1000) for i in xrange(n)]
    b_rep = [randint(0, 1000)]
    numbers = k_rep*k + b_rep*b
    shuffle(numbers)
    print "k_rep: ", k_rep
    print "b_rep: ", b_rep
    return numbers

def solve(data, k):
    cnts = [0]*10
    for number in data:
        bits = [number >> b & 1 for b in xrange(10)]
        cnts = [cnts[i] + bits[i] for i in xrange(10)]
    return reduce(lambda a,b:2*a+(b%k>0), reversed(cnts), 0)

print "Answer: ", solve(generate_test_data(10, 15, 13), 3)