我正在为 finding the majority element 编写摩尔投票算法的实现(即在数组中出现超过 size/2 次的元素)。代码应返回多数元素(如果存在)，否则应返回 -1。现在，如果我在 main() 函数中直接对整数数组进行硬编码并调用它，我的 majorityElement(int size, int arr[]) 版本似乎工作得很好从那里。
int majorityElement(int size, int arr[])
{
int majorityindex = 0;
int votes = 1;
int index;
for (index = 1; index < size; index++)
{
if (arr[index] == arr[majorityindex])
votes++;
else
votes--;
if (votes == 0)
{
majorityindex = index;
votes = 1;
}
}
int count = 0;
int i;
for (i = 0; i < size; i++)
{
if(arr[majorityindex] == arr[i])
count++;
}
if (count > (size/2))
return arr[majorityindex];
return -1;
}
但是，如果我尝试读取这样的输入流，我会遇到一些问题:
2
5
3 1 3 3 2
3
1 2 3
输入的第一行包含测试用例的数量。测试用例的第一行是数组的大小，第二行是数组的元素。
我尝试从 main() 函数中读取输入流，如下所示:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 100
int majorityElement(int size, int arr[]);
int main()
{
char buf[3];
fgets(buf, MAX, stdin);
int n = atoi(buf);
char a[3];
char b[MAX];
int i;
int count;
int* num;
for (i = 0; i < n; i++)
{
count = 0;
fgets(a, MAX, stdin);
fgets(b, MAX, stdin);
int x = atoi(a);
char* num[x];
int arr[x];
int k = 0;
char* token = strtok(b, " ");
while (token != NULL)
{
num[k] = token;
arr[k] = atoi(num[k]);
token = strtok(NULL, " ");
k++;
}
printf("%d\n", majorityElement(x, arr));
}
return 1;
}
我在声明期间将 buf[] 和 a[] 的大小设为 3，因为它们必须有足够的空间用于 \n 由 fgets() 读取的字符以及终止 \0 字符。据我所知，atoi() 函数在将字符数组(字符串)转换为整数时会忽略 \n 字符。我尝试将输入的第一个条目(即条目数)存储在字符数组 buf 中，将其转换为字符串并存储在变量 n 中。同样，我尝试在变量 x 中获取测试数组的大小，在整数数组 arr 中获取测试数组(测试用例的第二行)。虽然 buf 和 n 似乎在所有情况下都能获得正确的值，但我不太确定 arr。我知道 fgets() 会留下一个终端 \n 字符，并且 可能 在使用 strtok< 标记化期间造成一些破坏，虽然我不知道为什么。我尝试在 GeeksForGeeks 上提交此代码.它为示例测试用例提供了绝对正确的输出:
2
5
3 1 3 3 2
3
1 2 3
也就是
3
-1
但是，当我尝试“提交”我的解决方案时，它说:
Possibly your code doesn't work correctly for multiple test-cases (TCs).
The first test case where your code failed:
Input:
4
1 2 2 1
Its Correct output is:
-1
And Your Code's output is:
1
我似乎无法理解这一点。如果我在 stdin 中手动编写:
1
4
1 2 2 1
代码输出
-1
这确实是正确的解决方案。这与提交期间声明的输出不匹配，即 1。所以我不确定我哪里出错了。我是否在 main() 函数中错误地使用了 fgets() 或 strtok()？还是其他原因？
根据评论中的建议更新了main()函数。
int main()
{
char buf[MAX];
fgets(buf, MAX, stdin);
int n = atoi(buf);
char a[MAX];
char b[MAX];
int i;
int count;
int* num;
for (i = 0; i < n; i++)
{
count = 0;
fgets(a, MAX, stdin);
fgets(b, sizeof(a), stdin);
a[sizeof(a)-1] = '\0';
b[sizeof(b)-1] = '\0';
int x = atoi(a);
int arr[x];
int k = 0;
char* token = strtok(b, " ");
while (token != NULL)
{
if (k > x)
break;
arr[k] = atoi(token);
token = strtok(NULL, " ");
k++;
}
printf("%d\n", majorityElement(x, arr));
}
return 1;
}
正如@Vlad 所指出的，我的原始数组中的 MAX 设置得太低了。问题说数组中的条目数上限为 10^7，每个数组条目的上限为 10^6(7 位数字)。所以 MAX 需要是 10^8 的顺序。根据评论中的建议，我现在使用动态分配 而不是可变长度数组。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 10000000
int majorityElement(int size, int arr[])
{
int majorityindex = 0;
int votes = 1;
int index;
for (index = 1; index < size; index++)
{
if (arr[index] == arr[majorityindex])
votes++;
else
votes--;
if (votes == 0)
{
majorityindex = index;
votes = 1;
}
}
int count = 0;
int i;
for (i = 0; i < size; i++)
{
if(arr[majorityindex] == arr[i])
count++;
}
if (count > (size/2))
return arr[majorityindex];
return -1;
}
int main()
{
char* buf = calloc (MAX, sizeof(char));
fgets(buf, MAX, stdin);
int n = atoi(buf);
char* a = calloc (MAX, sizeof(char));
char* b = calloc(MAX, sizeof(char));
int i;
for (i = 0; i < n; i++)
{
fgets(a, MAX, stdin);
fgets(b, MAX, stdin);
a[strlen(a)-1] = '\0';
b[strlen(b)-1] = '\0';
int x = atoi(a);
int *arr = calloc(x, sizeof(int));
int k = 0;
char* token = strtok(b, " ");
while (token != NULL)
{
if (k > x)
break;
arr[k] = atoi(token);
token = strtok(NULL, " ");
k++;
}
printf("%d\n", majorityElement(x, arr));
free(arr)
}
free(buf);
free(a);
free(b);
return 1;
}
如果我将 MAX 设置为 10^7，那么代码将通过所有测试用例并被接受提交。但是，如果我将 MAX 设置为 10^8(根据需要)，则会出现段错误。如何克服这个问题？
最佳答案
您的程序有几个缺点。
例如在函数 main 中有一些未使用的变量声明如下
int count;
int* num;
该函数确实考虑到了 -1可以是数组的有效值。
测试中可指定的元素数量存在问题。这是一个非常大的数字(根据描述 1 <= N <= 10000000 )。所以 MAX 的值等于 100太低了。结果，数据可能被错误且不完整地读取。可变长度数组也可能会出现问题。
不需要使用函数fgets因为可以使用 scanf 读取每个整数.
我可以建议以下解决方案。尝试一下，看看它是否会通过测试。
#include <stdio.h>
#include <stdlib.h>
size_t majorityElement( const int a[], size_t n )
{
size_t majority_index = 0;
for ( size_t i = 1, votes = 1; i < n; i++ )
{
if ( a[majority_index] == a[i] )
{
++votes;
}
else
{
--votes;
}
if ( votes == 0 )
{
majority_index = i;
++votes;
}
}
size_t count = 0;
for ( size_t i = 0; i < n; i++ ) count += a[i] == a[majority_index];
return n / 2 < count ? majority_index : n;
}
int main(void)
{
size_t n = 0;
scanf( "%zu", &n );
for ( size_t i = 0; i < n; i++ )
{
size_t m = 0;
scanf( "%zu", &m );
if ( m != 0 )
{
int *a = calloc( m, sizeof( int ) );
for ( size_t j = 0; j < m; j++ ) scanf( "%d", a + j );
size_t majority_index = majorityElement( a, m );
printf( "%d\n", majority_index == m ? -1 : a[majority_index] );
free( a );
}
}
return 0;
}
如果它没有通过测试，那么它似乎在测试中存在错误。:)
或者如果函数返回类型不能改变那么函数定义可以看起来像
int majorityElement( const int a[], size_t n )
{
size_t majority_index = 0;
for ( size_t i = 1, votes = 1; i < n; i++ )
{
if ( a[majority_index] == a[i] )
{
++votes;
}
else
{
--votes;
}
if ( votes == 0 )
{
majority_index = i;
++votes;
}
}
size_t count = 0;
for ( size_t i = 0; i < n; i++ ) count += a[i] == a[majority_index];
return n / 2 < count ? a[majority_index] : -1;
}
关于c - 我对 fgets() 和 strtok() 的使用对于解析多行输入是否不正确？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/57626058/