问题描述
您有一个数组大小 N 和恒的 K （其他）
您可以假设该数组是int型（虽然它可以是任何类型的）
描述的重演，至少 N / K 次...如果有回报之一的算法发现，如果有一个元素（S）。在线性时间内这样做（ O（N））
美中不足的是：做用常量内存和运行在阵列只有两次这种算法（甚至是伪code）
-
创建大小的临时数组（K-1）存储元件和它们的计数（输出元件将是这些k-1个要素中）。
-
通过输入数组和遍历更新临时[]（添加/删除元素或增加/减少计数），每走过元素。数组临时[]商店电位（K-1）考生在每一步。这一步需要O（NK）的时间。
- 在遍历决赛（K-1）潜在候选人（存储在临时[]）。或者每一个元素，检查是否实际具有数超过N / K。这一步需要O（NK）的时间。
主要步骤是步骤2，如何维持（K-1）在每一点上的潜在候选人？在步骤2中使用的步骤，就像著名的游戏：俄罗斯方块。我们对待每一个数字作为片中的俄罗斯方块，这在我们的临时数组临时[]倒下。我们的任务是尽量保持堆叠在同一列中具有相同数目（在临时数组计数被递增）。
考虑K = 4，N = 9
由于阵：3 1 2 2 2 1 4 3 3
I = 0
3 _
临时[]有一个元素，用3计数1
I = 1
3 1 _
温度[]具有两个元件，3和1个同
计数1和1分别
设为i = 2
3 1 2
温度[]有三个要素，3，1和2与
计为分别1,1和1。
I = 3
- - 2
3 1 2
温度[]有三个要素，3，1和2与
计为分别1,1和2。
I = 4
- - 2
- - 2
3 1 2
温度[]有三个要素，3，1和2与
计为分别为1，1和3。
I = 5
- - 2
- 1 2
3 1 2
温度[]有三个要素，3，1和2与
计为分别为1，2和3。
现在的问题是，什么时候做临时[]已满，我们看到了一个新的元素 - 我们从栈元素，即去除最下面一排，我们在临时[]降低每一个元素的数量1。我们忽略当前元素。
与i = 6
- - 2
- 1 2
温度[]有两个元素，1和2与
计为1和2分别。
I = 7
- 2
3 1 2
温度[]有三个要素，3，1和2与
计为分别1,1和2。
I = 8
3 - 2
3 1 2
温度[]有三个要素，3，1和2与
计为分别2，1和2。
最后，我们最多有K-1在临时[]号。在临时的元素是{3,1，2}。请注意，在临时[]的数量现在已经没用了，是只需要在第2步计数现在，我们需要检查在临时[]元素的实际数量是否超过N / K（9/4）或没有。元件3和2具有比计数9/4以上。因此，我们打印3和2。
请注意，该算法不会错过任何输出元素。可以有两种可能性，许多事件是一起的或跨。数组s $ P $垫。如果出现在一起，再算上会很高，也不会成为0。如果出现有s $ P $垫，则该元素将再次进来温度[]。以下是C ++实现上述算法的。
// C ++程序打印与计数的元素大于N / K
＃包括＆LT;的iostream＆GT;
使用名字空间std;
//一个结构来存储一个元素和它当前的计
结构eleCount
{
INTê; // 元件
INT℃; // 计数
};
//打印要素超过N / K出现在ARR []的
//大小为n。如果没有这样的元素，那么就打印什么。
无效moreThanNdK（INT改编[]，INT N，INT K）
{
//ķ必须大于1，以获得一些输出
如果（K 2）
返回;
/ *第1步：创建一个临时数组（包含的元素
和计数大小为k-1）。初始化所有的数
元素0 * /
结构eleCount温度[K-1];
的for（int i = 0; I＆LT; K-1;我++）
临时[I] .C = 0;
/ *第2步：过程输入数组的所有元素* /
的for（int i = 0;我n种;我++）
{
诠释J;
/ *如果ARR [我]已经present在
元素计数的数组，然后增加其计数* /
为（J = 0; J＆LT; K-1，J ++）
{
如果（临时[J]。E ==改编[I]）
{
温度[J]。C + = 1;
打破;
}
}
/ *如果ARR [我]不是present在临时[] * /
如果（j == K-1）
{
INT升;
/ *如果在临时使用的位置[]，然后将
改编[i]于第一个可用的位置，并设置数量为1 * /
为（升= 0; L＆所述K-1;升++）
{
如果（临时[L] .C == 0）
{
临时[L] .E =改编[I]
温度[升]的.c = 1;
打破;
}
}
/ *如果在temp []所有的位置都填满，然后
减1的每一个元素的数量* /
如果（升== K-1）
为（升= 0; L＆所述; k;升++）
温度[升]的.c - = 1;
}
}
/ *第三步：检查潜在候选人的实际数量在温度[] * /
的for（int i = 0; I＆LT; K-1;我++）
{
//计算元素的实际计数
INT交流= 0; //实际计数
为（诠释J = 0; J＆n种; J ++）
如果（ARR [J] ==温度[I] .E）
AC ++;
//如果实际数超过N / K，然后打印
如果（交流将N / k）的
COUT＆LT;＆LT; 号码：＆LT;＆LT;临时[I] .E
＆LT;＆LT; 伯爵：＆LT;＆LT; AC＆LT;＆LT; ENDL;
}
}
/ *驱动程序测试上面的函数* /
诠释的main（）
{
COUT＆LT;＆LT; 第一个测试\ N的;
INT ARR1 [] = {4，5，6，7，8，4,4};
INT大小= sizeof的（ARR1）/ sizeof的（ARR1 [0]）;
INT K = 3;
moreThanNdK（ARR1，大小，k）的;
COUT＆LT;＆LT; \ n第二测试\ N的;
INT ARR2 [] = {4,2，2，7};
大小= sizeof的（ARR2）/的sizeof（ARR2 [0]）;
k = 3的;
moreThanNdK（ARR2，大小，k）的;
COUT＆LT;＆LT; \ nThird测试\ N的;
INT ARR3 [] = {2,7，2};
大小= sizeof的（ARR3）/的sizeof（ARR3 [0]）;
K = 2;
moreThanNdK（ARR3，大小，k）的;
COUT＆LT;＆LT; \ nFourth测试\ N的;
INT arr4 [] = {2,3，3，2};
大小= sizeof的（arr4）/的sizeof（arr4 [0]）;
k = 3的;
moreThanNdK（arr4，大小，k）的;
返回0;
}
You have an array size n and a constant k (whatever)
You can assume the the array is of int type (although it could be of any type)
Describe an algorithm that finds if there is an element(s) that repeats itself at least n/k times... if there is return one. Do so in linear time (O(n))
The catch: do this algorithm (or even pseudo-code) using constant memory and running over the array only twice
Create a temporary array of size (k-1) to store elements and their counts (The output elements are going to be among these k-1 elements).
Traverse through the input array and update temp[] (add/remove an element or increase/decrease count) for every traversed element. The array temp[] stores potential (k-1) candidates at every step. This step takes O(nk) time.
- Iterate through final (k-1) potential candidates (stored in temp[]). or every element, check if it actually has count more than n/k. This step takes O(nk) time.
The main step is step 2, how to maintain (k-1) potential candidates at every point? The steps used in step 2 are like famous game: Tetris. We treat each number as a piece in Tetris, which falls down in our temporary array temp[]. Our task is to try to keep the same number stacked on the same column (count in temporary array is incremented).
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.
Finally, we have at most k-1 numbers in temp[]. The elements in temp are {3, 1, 2}. Note that the counts in temp[] are useless now, the counts were needed only in step 2. Now we need to check whether the actual counts of elements in temp[] are more than n/k (9/4) or not. The elements 3 and 2 have counts more than 9/4. So we print 3 and 2.
Note that the algorithm doesn’t miss any output element. There can be two possibilities, many occurrences are together or spread across the array. If occurrences are together, then count will be high and won’t become 0. If occurrences are spread, then the element would come again in temp[]. Following is C++ implementation of above algorithm.
// 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;
}
这篇关于发现，如果有一个元件重演N / k次的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！