arrays - 数组中的稀有元素

Question

给定一个由 n 个整数组成的有序数组 A[1..n]。如果元素 x E A 出现，我们说它是稀有的在 A 中严格小于 n/10 次。也就是说，如果存在某个索引 1 <= i <= n 使得 x 是罕见的A(i) = x，并且严格少于 n/10 个不同的索引 j，其中 A(j) = x。我们的目标就是找一个稀有元素，或者输出A不包含稀有元素。

输入:一个由 n 个整数组成的排序数组 A[1..n]。

输出:稀有元素x E A，或者输出“No rare element exists in A.”

是否有针对稀有元素问题的 O(log n) 时间算法？这是什么？

T(n) = 10 T(n/10) + O(1) 给出 O(n) 的时间，这对我来说不够好。

Answer 1

是的，可以在 O(log n) 中完成。我假设，你已经在内存中有了这个数组。否则不可能比 O(n) 更快，因为您至少需要读取数组。

假设 step 是小于 n/10 的最大整数。如果 step 等于零，那么我们显然没有稀有元素。

考虑以下算法:

int start = 1;
while (true) {
  if (n - start + 1 <= step) {
    OutputRare(A[start]); Exit;
  }
  int next_index = start + step;
  if (A[start] != A[next_index]) {
    OutputRare(A[start); Exit;
  }
  // Here we need to find the smallest index starting from start with
  // element that is not equal to A[start]. If such element does not
  // exist function returns -1.
  next_index = FindFirstNonEqual(A[start], start);
  if (next_index == -1) {
    // There is no rare elements
    Exit;
  }
  start = next_index;
}

此算法要么返回稀有元素，要么至少增加 step 开始。这意味着它将增加 start ~10 倍(因为每一步大约是 n/10)。 FindFirstNonEqual 可以使用二进制搜索来实现，这意味着总复杂度为 O(10log n) = O(log n)。