我正在尝试解决 CTS 招聘活动中提出的问题之一。我给出的代码有一些错误。在不修改方法和不使用任何附加库的情况下，我必须解决问题。
就是去掉重复元素，只让第一次出现的整数在数组上。
告诉我我在这里做错了什么？
给出的错误代码：
#include<stdio.h>
#include<stdlib.h>
typedef struct node {
int arr[1000];
int len;
} Numbers;
void* deleteDuplicate (int *arr, int len)
{
int count=0,p,i,j,k,originalLength=len;
for(i=0; i<len; i++)
{
for(j=i+1; j<len; j++)
{
if(arr[j]==arr[i])
{
arr[k]=arr[k+1];
}
len=len-1;
count=count+1;
j=i;
}
}
int newLength = originalLength-count;
Numbers *numbers = malloc(sizeof(*numbers));
for(i=0; i<newLength; i++)
numbers->arr[i]=arr[i];
numbers->len = newLength;
return numbers;
}
int main() {
int arr[]={2,3,2,2,5,6,6,7};
Numbers *n = deleteDuplicate(arr,8);
for(int i=0;i<n->len;i++){
printf("%d ",arr[i]);
}
}
我的解决方案：
#include<stdio.h>
#include<stdlib.h>
typedef struct node {
int arr[1000];
int len;
} Numbers;
void* deleteDuplicate (int *arr, int len)
{
int count=0,p,i,j,k,originalLength=len;
for(i=0; i<len; i++)
{
for(j=i+1; j<len; j++)
{
if(arr[j]==arr[i])
{
for(k=j;k<len-1;k++)
arr[k]=arr[k+1];
len=len-1;
count=count+1;
j=i;
}
}
}
int newLength = originalLength-count;
Numbers *numbers = malloc(sizeof(*numbers));
for(i=0; i<newLength; i++)
numbers->arr[i]=arr[i];
numbers->len = newLength;
return numbers;
}
int main() {
int arr[]={2,3,2,2,5,6,6,7};
Numbers *n = deleteDuplicate(arr,8);
for(int i=0;i<n->len;i++){
printf("%d ",arr[i]);
}
}
我的解决方案仅提供某些情况下的输出。
您的问题可能出在
main()printf("%d ",arr[i]);
您正在从初始数组打印，而不是从您填充的返回结构体数组打印...
printf( "%d ", n->arr[i] );
查看此问题的另一种方法是该函数必须返回一个分配的结构。 如果你首先这样做（注意：
calloc()typedef struct node {
int arr[1000];
int len;
} Numbers;
Numbers *deleteDuplicates( int *arr, int len ) {
Numbers *pRet = calloc( 1, sizeof *pRet );
if( pRet == NULL ) // ALWAYS test return values.
exit( -1 );
pRet->arr[ pRet->len++ ] = arr[0]; // first one is free
for( int i = 1; i < len; i++ ) {
for( int j = 0; j < pRet->len; j++ )
if( arr[i] == pRet->arr[j] ) // seen before?
break;
if( j == pRet->len ) // Hmm... Not seen before!
pRet->arr[ pRet->len++ ] = arr[i];
}
return pRet;
}
int main( void ) {
int arr[] = { 2, 3, 2, 2, 5, 6, 6, 7 };
Numbers *n = deleteDuplicates( arr, 8 );
if( n == NULL )
exit( -1 );
for( int i = 0; i < n->len; i++ )
printf( "%d ", n->arr[i] );
putchar( '\n' );
free( n ); // don't forget!
return 0;
}
输出：
2 3 5 6 7
不需要第二个（可能很大）并行阵列的替代版本。这会“找到”一个未出现在数组中的“哨兵值”，然后使用它来将重复值进一步破坏到数组中。然后它会压缩原始数组中的（现在是唯一的）值。对函数签名进行了一些调整以与结构定义保持一致（也进行了更改），以及一些“调试”打印语句只是为了好玩。
#include <stdio.h>
#include <stdlib.h>
typedef struct { // use simpler typedef. Not a "node"
int *arr; // more flexible than fixed size
size_t len; // use size_t for size, not signed int
} Numbers_t; // conventional name style with "_t"
// Find a value that does NOT appear in the data
int findSentinel( int a[], size_t sz ) {
int val;
// deliberate collision starting with 2 to prove function
// more sensible to start with INT_MIN, or maybe INT_MAX (from limits.h)
for( val = 2; val < 1000 * 1000; val++ ) {
printf( "Sentinel %d ? ", val ); // debugging
for( size_t i = 0; i < sz && a[i] != val; i++ )
; // searching
// Good? return, else keep searching
if( i == sz ) { puts( "YES!" ); return val; }
puts( "Nope..." );
}
// may not be able to use this technique
fprintf( stderr, "Cannot find a sentinel value\n" );
exit( EXIT_FAILURE );
return -1; // quiet compiler warning
}
// Notice changed function signature using struct declaration
Numbers_t *deleteDuplicates( Numbers_t *n ) {
size_t i, j;
int sntnl = findSentinel( n->arr, n->len );
printf( "Sentinel value (%d)\n", sntnl );
// iterative search and replace of 2nd, 3rd... instances of array values
for( i = 0; i < n->len; i++ ) {
int got = n->arr[i];
if( got == sntnl ) continue; // skip over these
for( j = i+1; j < n->len; j++ )
if( n->arr[j] == got ) { // seen before?
printf( "%d dupe @ pos %d\n", got, j+1 ); // debug
n->arr[j] = sntnl; // clobber duplicate
}
}
// compact the array to unique values
for( i = j = 0; i < n->len; i++ )
if( n->arr[i] != sntnl )
n->arr[j++] = n->arr[i];
n->len = j; // array may have fewer elements now
return n;
}
// helper function
void printArr( Numbers_t *n ) {
for( size_t i = 0; i < n->len; i++ )
printf( "%d ", n->arr[i] );
putchar( '\n' );
}
int main( void ) {
int arr[] = { 2, 3, 2, 2, 5, 6, 6, 7 };
// fill provided struct with sample data
Numbers_t n = { arr, sizeof arr/sizeof arr[0] };
printArr( &n );
deleteDuplicates( &n );
printArr( &n );
return 0;
}
输出
2 3 2 2 5 6 6 7
Sentinel 2 ? Nope...
Sentinel 3 ? Nope...
Sentinel 4 ? YES!
Sentinel value (4)
2 dupe @ pos 3
2 dupe @ pos 4
6 dupe @ pos 7
2 3 5 6 7
a[0]的值是唯一的。该值可以充当我所说的“哨兵值”...这消除了循环
猜测什么可能有效的需要...
findSentinel()消失了，这个函数改变了3行：
// Notice changed function signature using struct declaration
void deleteDuplicates( Numbers_t *n ) {
size_t i, j;
int sntnl = n->arr[0];
printf( "Sentinel value (%d)\n", sntnl );
// iterative search and replace of 2nd, 3rd... instances of array values
for( i = 1; i < n->len; i++ ) {
int got = n->arr[i];
if( got == sntnl ) continue; // skip over these
for( j = i+1; j < n->len; j++ )
if( n->arr[j] == got ) { // seen before?
printf( "%d dupe @ pos %d\n", got, j+1 ); // debug
n->arr[j] = sntnl; // clobber duplicate
}
}
// compact the array to unique values
for( i = j = 1; i < n->len; i++ )
if( n->arr[i] != sntnl )
n->arr[j++] = n->arr[i];
n->len = j; // array may have fewer elements now
}