0

我不是在问如何在数组中找到多数元素，这已在此处详细讨论过查找数组中的多数元素

我的问题如下：

有一个数组arr[1...2n]，这个数组的多数元素是maj，现在我将使用以下规则删除其中的元素arr，

如果arr[i] == arr[i + 1], 删除arr[i], i = 1, 3, 5,..., 2n - 1; else if arr[i] != arr[i + 1], 删除arr[i]and arr[i + 1], i = 1, 3, 5, ..., 2n - 1。

那么我们可以得到一个新的数组new_arr，多数元素的候选new_arr是new_maj，有什么证据可以证明new_maj == maj吗？

4

3 回答 3

1

是的，有证据。

我们只对元素对感兴趣a[i],a[i+1]，i奇怪。如果a[i]=a[i+1]，我们称这样的一对“好”。其他对是“坏的”。等于多数候选的元素是“groovy”。一对好的 groovy 元素是一对 groovy。

关于好对子的一个简单事实是，至少有一半的好对子是时髦的。假设不是这样；那么在好的对中，只有不到一半的元素是 groovy 的，而在坏的对中，不超过一半的元素是 groovy 的。总的来说，只有不到一半的元素是 groovy 的。这是一个矛盾。

所以我们已经确定，至少有一半的好对子是 groovy 的。

现在消除所有坏对。仍然至少有一半的元素是 groovy 的（因为只剩下好的对，其中至少有一半是 groovy 的）。

现在从好对中消除所有其他元素。仍然至少有一半的元素是常规的（因为每个元素的数量只是减半）。

证明到此结束。

于 2013-04-18T18:21:45.857 回答
0

这是我的证明变体：

考虑对 arr[i] 和 arr[i+1] 的 4 种情况（反之亦然，对的顺序并不重要）， i 是奇数。设maj是主要元素，min是任何次要元素：

  1. maj maj - 让这些对的数量为
  2. maj min - 设此类对的数量为b
  3. min1 min2 - 让这些对的数量为c , min1 != min2
  4. min1 min1 - 让此类对的数量为d

a、b、c、d 都 >= 0。

案例 1 对主要元素的原始总和贡献 2 |maj| 并减少主要元素的最终总和 |maj|' （算法执行后）乘以 1

案例 2 对 |maj| 贡献 1 和 1 到 |min|，所有次要元素的原始总和，并减少 |maj|' 由 1 和 |min|' 1

案例 3 对 |min| 贡献 2 并减少 |min|' 2

案例 4 对 |min| 贡献 2 并减少 |min|' 1

因此，原始数组 arr[] 中主要元素的总数为：

|maj| = 2a + b

而所有次要元素的数量为：

|min| = b + 2c + 2d

自从 |maj| > |分钟| ,

2a + b > b + 2c + 2d
    2a > 2c + 2d
     a > c + d

运行算法后，新的主要元素数由下式给出：

|maj|' = |maj| - a - b

新的次要元素数量为：

|min|' = |min| - b - 2c - d

代入我们得到：

|maj|' = 2a + b - a - b           = a
|min|' = b + 2c + 2d - b - 2c - d = d

由于我们从上面知道c + d < a，并且a，c，d都> = 0，所以我们有

a > c + d =>
a > d =>
|maj|' > |min|'

因此maj仍然是新数组中的主要元素。

于 2013-04-18T19:07:18.130 回答
0

定义N = 2 n. 数组包含N元素。

定义为出现在数组中M的次数。maj“多数元素”的定义是M > N/2。

现在将数组分成对p[1] ... p[n]。定义q0为包含 的零个实例的对数maj。定义q1为恰好包含 的一个实例的对数maj。定义q2为恰好包含 的两个实例的对数maj。

然后N = 2 q0 + 2 q1 + 2 q2和M = q1 + 2 q2。

代入定义多数元素的不等式，并简化：

        M > N / 2
q1 + 2 q2 > (2 q0 + 2 q1 + 2 q2) / 2
q1 + 2 q2 > q0 + q1 + q2
     2 q2 > q0 + q2
       q2 > q0

因此，包含 的两个实例的对maj的数量超过了包含 的零实例的对的数量maj。

现在定义为运行算法后出现在新数组中M'的次数。maj该算法为每一对删除一个，为maj每一q1对删除一个。所以。majq2M' = M - q1 - q2

定义N'为算法生成的新数组的大小。该算法为每对删除两个元素，为每q1对删除一个元素q2。

但是我们不知道算法为每一q0对删除了多少元素。一些q0对包含两个不同的元素，算法会删除这两个元素。但其他q0对包含相同的（非maj）元素，算法只删除一个。

一个极端是所有q0对都被完全删除。在这种情况下，算法会删除2 q0元素，所以

N - 2 q1 - q2 - 2 q0 ≤ N'

另一个极端是每q0对只删除一个元素。在这种情况下，算法会删除q0元素，所以

N - 2 q1 - q2 - q0 ≥ N'

让我们回到“多数元素”的定义，做一些代数：

          M > N / 2
M - q1 - q2 > N / 2 - q1 - q2
M - q1 - q2 > (N - 2 q1 - 2 q2) / 2
M - q1 - q2 > (N - 2 q1 - q2 - q2) / 2

左边是M'。

M' > (N - 2 q1 - q2 - q2) / 2

我们可以把右手边变成N' / 2吗？首先，两边都乘以 2：

2 M' > N - 2 q1 - q2 - q2

回想一下，我们证明了q2 > q0. 所以

2 M' > N - 2 q1 - q2 - q2 > N - 2 q1 - q2 - q0

并且，由于我们推断N - 2 q1 - q2 - q0 ≥ N'，

2 M' > N - 2 q1 - q2 - q0 ≥ N'

所以

2 M' > N'
  M' > N' / 2

因此maj在新数组中出现了足够的时间成为新数组的多数元素。QED。

于 2013-04-18T16:09:35.107 回答