arrays - 在大小为 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

数组:2 2 2 3 3 3 1 1

输出:1

Answer 1

我假设:

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

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

递归步骤:在线性时间内找到当前数组切片的中值元素，就像在快速排序中一样。令中位数元素为M。

在递归步骤之后，您得到一个数组，其中所有小于 M 的元素都出现在 M 第一次出现的左侧。所有 M 元素彼此相邻，所有大于 M 的元素都出现在所有出现的右侧M.

查看最左边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.Array = {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} 有3左边的6个元素。6是k=3的倍数。所以每个元素必须在那里出现 3 次。所以S>=3。在右侧递归。等等。