数组中最大元素的分治算法（O(N.log(N))）

Question

给定一个包含N个元素（可重复）的数组a []，如果其内容中超过一半等于v，则称其“大部分包含一个v元素”。 给定数组a []，需要设计一个高效的算法（时间为N.log（N），使用分治法），以检查它是否包含多数元素并确定它。请注意，数组元素之间唯一可用的比较操作是相等性（a [i] == a [j]），执行时间为常数。 （提示：在算法中，将数组[]划分为两个子数组a1 []和a2 []，每个子数组大小为a []的一半。如果a []中大多数元素是v，则v也必须是a1 []，a2 []或两者都是多数元素）。

int main() {

    int a[12] = {5, 9, 3, 13, 5, 21, 5, 7, 17, 12, 5, 6};
    int N = 12, lo = 0, hi = N - 1, mid,i,j;

    mid = lo + (hi - lo) / 2;
    int n1 = mid - lo + 1;
    int n2 =  hi - mid;
    int a1[n1],a2[n2];

    /* Copy data to temp arrays a1[] and a2[] */
    for (i = 0; i < n1; i++)
        a1[i] = a[lo + i];
    for (j = 0; j < n2; j++)
        a2[j] = a[mid+1+j];


    while (i < n1 && j < n2) {

        if(a1[i]==a2[j]){

        }else if(){


        }else{


        }

    }
    return 0;
}

我在使用辅助数组进行等式比较操作时遇到了困难，需要确定最大元素是在 a1[] 还是 a2[] 中，或者同时存在于两个数组中。

- CodeOnce

---

@AlbinPaul 看起来 OP 不允许排序。他不能使用除相等以外的其他比较方式。 - kyriakosSt

如果一个数组a[]中的大多数元素是v，那么v也必须是a1[]或a2[]或两者中大多数元素。然而，逆推不成立：即使v在a1[]中是大多数，它也不一定是a[]中的大多数。 - JimmyB

需要使用分治算法吗？这里有一个线性算法。 - user58697

Answer 1

这里是一个符合描述的 Python 实现（抱歉，我不熟悉 C，但我认为代码很简单）。我们可以跟随记录的返回值和每个被检查部分的索引，以理解它的工作原理。

# Returns v if v is a majority;
# otherwise, returns None
def f(arr, low, high):
  if low == high:
    return arr[low]

  if low + 1 == high:
    return arr[low] if arr[low] == arr[high] else None

  n = high - low + 1
  mid = (low + high) / 2

  l = f(arr, low, mid)
  r = f(arr, mid + 1, high)

  print 'n: ' + str(n) + '; l: ' + str(l) + '; r: ' + str(r) + '; L: ' + str((low, mid)) + '; R: ' + str((mid + 1, high))

  if l == r:
    return l

  counts = [0, 0]

  for i in xrange(low, high + 1):
    if arr[i] == l:
      counts[0] = counts[0] + 1
    if arr[i] == r:
      counts[1] = counts[1] + 1

  if l and counts[0] * 2 > n:
    return l

  if r and counts[1] * 2 > n:
    return r

  return None

输出：

a = [5, 9, 3, 5, 5, 21, 5, 7, 17, 5, 5, 5]

print f(a, 0, len(a) - 1)

"""
n: 3; l: None; r: 3; L: (0, 1); R: (2, 2)
n: 3; l: 5; r: 21; L: (3, 4); R: (5, 5)
n: 6; l: None; r: 5; L: (0, 2); R: (3, 5)
n: 3; l: None; r: 17; L: (6, 7); R: (8, 8)
n: 3; l: 5; r: 5; L: (9, 10); R: (11, 11)
n: 6; l: None; r: 5; L: (6, 8); R: (9, 11)
n: 12; l: None; r: 5; L: (0, 5); R: (6, 11)
5
"""

- גלעד ברקן

Answer 2

我认为这个函数应该做到以下几点：

1）对数组的前一半进行递归调用（返回答案a）

2）对数组的后一半进行递归调用（返回答案b）

3）循环遍历数组，计算匹配a/b的数量，并返回匹配数量最多的那个

请注意，没有必要在任何阶段复制数组，因为它从未被修改，只需传入开始和子数组长度的索引即可。

- Peter de Rivaz

---

我认为您的描述会针对输入1, 1, 1, 2, 2, 3返回1。但是1不是大多数。 - גלעד ברקן

我会进行点踩操作，直到您解决这个问题 :) - גלעד ברקן

Answer 3

这可能不是你想要的答案。但是有一种有趣的概率方法可以解决这个问题。

你可以选择数组的某个位置x，并计算数组[x]出现的次数，以检查它是否出现了>= array.size() / 2次。

如果有一个元素填满了超过一半的数组，则随机选择它的位置的概率每次迭代都> 1/2。

因此，如果你做30次迭代之类的事情，选择“支配”元素的机会就是(1 - (1/2)^30)，这对于几乎所有应用程序来说都是可以接受的。

复杂度为O(numberOfIterations * arraySize)

这里是代码(:。

它是用C++编写的，但我敢打赌你可以轻松将其翻译成C。

#include <vector>
#include <iostream>


int arraySize, numberOfIterations;

int count(int element, std::vector<int>& array)
{
    int count = 0;
    for(const int& number : array)
    {
        count += (number == element);
    }
    return count;
}


int main(){

    srand(time(0));

    std::cin >> arraySize;
    std::vector<int> arr(arraySize);

    for(int i = 0; i < arraySize; ++i)
    {
        std::cin >> arr[i];
    }

    std::cin >> numberOfIterations;

    for(int i = 0; i < numberOfIterations; ++i)
    {
        int idx = rand() % arraySize;
        int freq = count(arr[idx], arr);
        //std::cout << idx << std::endl;
        if(freq > arraySize / 2)
        {
            std::cout << "The element = " << arr[idx] << " dominates the array provided " << std::endl;
            return 0;
        }
    }
    return 0;
}

- Francisco Geiman