查找是否有一个元素重复n/k次

Question

你有一个数组大小n和一个常量 k(无论如何)

您可以假设该数组是int类型(尽管它可以是任何类型)

描述一种算法,该算法可以查找是否存在至少重复一次的元素n/k...如果有返回的元素.在线性时间(O(n))中这样做

问题:使用常量内存执行此算法(甚至伪代码)并仅在阵列上运行两次

Answer 1

我不是百分百肯定,但听起来你想要解决布兰妮斯皮尔斯问题 -使用常量记忆找到构成某个样本的某个部分的项目.

以下是对英文问题的陈述,并附有解决方案草图:

......来自麻省理工学院的Erik D. Demaine和加拿大滑铁卢大学的AlejandroLópez-Ortiz和J. Ian Munro的2002年文章.Demaine和他的同事扩展了算法以涵盖更一般的问题:给定长度为n的流,识别一组大小为m,其中包括频率大于n /(m + 1)的所有元素.(在m = 1的情况下,这会减少到多数问题.)扩展算法需要m个寄存器用于候选元素以及m个计数器.基本操作方案类似于多数算法.当流元素与候选者之一匹配时,相应的计数器递增; 当任何候选人都没有匹配时,所有的计数器都会减少; 如果计数器为0,

Answer 2

1. 创建一个大小(k-1)的临时数组来存储元素及其计数(输出元素将在这些k-1元素中).

2. 遍历输入数组并更新每个遍历元素的temp [](添加/删除元素或增加/减少计数).数组temp []在每一步都存储潜在的(k-1)候选者.此步骤需要O(nk)时间.

3. 迭代最终(k-1)个潜在候选者(存储在temp []中).或每个元素,检查它是否实际计数超过n/k.此步骤需要O(nk)时间.

主要步骤是步骤2,如何在每个点保持(k-1)潜在候选人？步骤2中使用的步骤就像着名的游戏:俄罗斯方块.我们将每个数字视为俄罗斯方块中的一个部分,它在我们的临时数组temp []中落下.我们的任务是尝试将相同的数字堆叠在同一列上(临时数组中的计数递增).

Consider k = 4, n = 9 
Given array: 3 1 2 2 2 1 4 3 3 

i = 0
         3 _ _
temp[] has one element, 3 with count 1

i = 1
         3 1 _
temp[] has two elements, 3 and 1 with 
counts 1 and 1 respectively

i = 2
         3 1 2
temp[] has three elements, 3, 1 and 2 with
counts as 1, 1 and 1 respectively.

i = 3
         - - 2 
         3 1 2
temp[] has three elements, 3, 1 and 2 with
counts as 1, 1 and 2 respectively.

i = 4
         - - 2 
         - - 2 
         3 1 2
temp[] has three elements, 3, 1 and 2 with
counts as 1, 1 and 3 respectively.

i = 5
         - - 2 
         - 1 2 
         3 1 2
temp[] has three elements, 3, 1 and 2 with
counts as 1, 2 and 3 respectively. 
Now the question arises, what to do when temp[] is full and we see a new element – we remove the bottom row from stacks of elements, i.e., we decrease count of every element by 1 in temp[]. We ignore the current element.

i = 6
         - - 2 
         - 1 2 
temp[] has two elements, 1 and 2 with
counts as 1 and 2 respectively.

i = 7
           - 2 
         3 1 2 
temp[] has three elements, 3, 1 and 2 with
counts as 1, 1 and 2 respectively.

i = 8          
         3 - 2
         3 1 2 
temp[] has three elements, 3, 1 and 2 with
counts as 2, 1 and 2 respectively.

最后,我们在temp []中最多有k-1个数字.temp中的元素是{3,1,2}.请注意,temp []中的计数现在没用,仅在步骤2中需要计数.现在我们需要检查temp []中元素的实际计数是否大于n/k(9/4).元素3和2的计数超过9/4.所以我们打印3和2.

请注意,该算法不会遗漏任何输出元素.可能有两种可能性,许多事件在一起或分布在整个阵列中.如果出现在一起,那么count将很高并且不会变为0.如果发生了遍历,则元素将再次出现在temp []中.以下是上述算法的C++实现.

// A C++ program to print elements with count more than n/k
#include<iostream>
using namespace std;

// A structure to store an element and its current count
struct eleCount
{
    int e;  // Element
    int c;  // Count
};

// Prints elements with more than n/k occurrences in arr[] of
// size n. If there are no such elements, then it prints nothing.
void moreThanNdK(int arr[], int n, int k)
{
    // k must be greater than 1 to get some output
    if (k < 2)
       return;

    /* Step 1: Create a temporary array (contains element
       and count) of size k-1. Initialize count of all
       elements as 0 */
    struct eleCount temp[k-1];
    for (int i=0; i<k-1; i++)
        temp[i].c = 0;

    /* Step 2: Process all elements of input array */
    for (int i = 0; i < n; i++)
    {
        int j;

        /* If arr[i] is already present in
           the element count array, then increment its count */
        for (j=0; j<k-1; j++)
        {
            if (temp[j].e == arr[i])
            {
                 temp[j].c += 1;
                 break;
            }
        }

        /* If arr[i] is not present in temp[] */
        if (j == k-1)
        {
            int l;

            /* If there is position available in temp[], then place 
              arr[i] in the first available position and set count as 1*/
            for (l=0; l<k-1; l++)
            {
                if (temp[l].c == 0)
                {
                    temp[l].e = arr[i];
                    temp[l].c = 1;
                    break;
                }
            }

            /* If all the position in the temp[] are filled, then 
               decrease count of every element by 1 */
            if (l == k-1)
                for (l=0; l<k; l++)
                    temp[l].c -= 1;
        }
    }

    /*Step 3: Check actual counts of potential candidates in temp[]*/
    for (int i=0; i<k-1; i++)
    {
        // Calculate actual count of elements 
        int ac = 0;  // actual count
        for (int j=0; j<n; j++)
            if (arr[j] == temp[i].e)
                ac++;

        // If actual count is more than n/k, then print it
        if (ac > n/k)
           cout << "Number:" << temp[i].e
                << " Count:" << ac << endl;
    }
}

/* Driver program to test above function */
int main()
{
    cout << "First Test\n";
    int arr1[] = {4, 5, 6, 7, 8, 4, 4};
    int size = sizeof(arr1)/sizeof(arr1[0]);
    int k = 3;
    moreThanNdK(arr1, size, k);

    cout << "\nSecond Test\n";
    int arr2[] = {4, 2, 2, 7};
    size = sizeof(arr2)/sizeof(arr2[0]);
    k = 3;
    moreThanNdK(arr2, size, k);

    cout << "\nThird Test\n";
    int arr3[] = {2, 7, 2};
    size = sizeof(arr3)/sizeof(arr3[0]);
    k = 2;
    moreThanNdK(arr3, size, k);

    cout << "\nFourth Test\n";
    int arr4[] = {2, 3, 3, 2};
    size = sizeof(arr4)/sizeof(arr4[0]);
    k = 3;
    moreThanNdK(arr4, size, k);

    return 0;
}