[已解决]本题原始代码有误，请各位帮忙解答，谢谢！

Kitty喜欢小鱼干 · 发表于 2018-8-13 14:17:54

最佳答案

月排行榜 / 总排行榜

ZKD

2018-8-13 14:17:55

#include<stdio.h>
#include<stdlib.h>
int str2set(int *lite, int length)
{
int i, j, temp_length = 0;
int in_flag = 0;//1 is true, 0 is false
int temp[length];
for(i = 0;i < length; i++)
{
for(j = 0; j < temp_length; j++)
{
if(lite[i] == temp[j])
{
in_flag = 1;
break;
}
}
if(in_flag == 0)
{
temp[j] = lite[i];
temp_length++;
}
in_flag = 0;
}
return temp_length;
}
int str2set_forsorted(int *lite, int length)
{
int i, max, j = 0;
int in_flag = 0;
int temp[length];
max = lite[0];
for(i = 0; i < length; i++)
{
if(lite[i] > max)
{
temp[j] = max;
j++;
max = lite[i];
}
}
j++;
return j;
}
int main()
{
int A[8] = {1, 2, 2, 3, 3, 4, 4, 4};
int res;
res = str2set_forsorted(A, 8);
printf("The length of str2set is: %d",res);
return 0;
}

复制代码

str2set是没有排序的数组变成集合的函数，需要两层嵌套循环，所以时间复杂度是O(N^2)。

而至于str2set_forsorted是排序之后的数组变成集合的函数，我默认是从小到大排序了。其实这是一个打擂台找最大值/最小值的问题，一旦有新的最大/最小值就需要将其写入数组当中，并更新长度计数器。

此函数用codeblocks测试过，但是我测试的样本较少，可能对某些数组有bug，请您指出。

跳转到最佳答案楼层

ZKD · 发表于 2018-8-13 14:17:55

#include<stdio.h>
#include<stdlib.h>
int str2set(int *lite, int length)
{
int i, j, temp_length = 0;
int in_flag = 0;//1 is true, 0 is false
int temp[length];
for(i = 0;i < length; i++)
{
for(j = 0; j < temp_length; j++)
{
if(lite[i] == temp[j])
{
in_flag = 1;
break;
}
}
if(in_flag == 0)
{
temp[j] = lite[i];
temp_length++;
}
in_flag = 0;
}
return temp_length;
}
int str2set_forsorted(int *lite, int length)
{
int i, max, j = 0;
int in_flag = 0;
int temp[length];
max = lite[0];
for(i = 0; i < length; i++)
{
if(lite[i] > max)
{
temp[j] = max;
j++;
max = lite[i];
}
}
j++;
return j;
}
int main()
{
int A[8] = {1, 2, 2, 3, 3, 4, 4, 4};
int res;
res = str2set_forsorted(A, 8);
printf("The length of str2set is: %d",res);
return 0;
}

复制代码

str2set是没有排序的数组变成集合的函数，需要两层嵌套循环，所以时间复杂度是O(N^2)。

而至于str2set_forsorted是排序之后的数组变成集合的函数，我默认是从小到大排序了。其实这是一个打擂台找最大值/最小值的问题，一旦有新的最大/最小值就需要将其写入数组当中，并更新长度计数器。

此函数用codeblocks测试过，但是我测试的样本较少，可能对某些数组有bug，请您指出。

无符号整形 · 发表于 2018-8-13 14:17:55

1.

#include<memory.h>
//未测试，或许有bug，请指出，谢谢！
int arr(int* array,int size)
{
int* a = malloc(size);//重复列表
int* result = malloc(size);//结果
memset(a,0,sizeof(int) * size);
memset(result,0,sizeof(int) * size);
int i,j,count = 0,flag = 0,rsize = 0;//count：j的有效位数，flag：发现重复后置1
for(i = 0;i < size;i++)
{
for(j = 0;j < count;j++)
{
if(array[i] == a[j])//发现重复！
{
flag = 1;
break;
}
}
if(count == 0)
{
count++;
result[i] = array[i];
rsize++;
a[i] = array[i];
continue;
}
if(!flag)//没有重复
{
result[i] = array[i];
a[i] = array[i];
rsize++;
}
}
return rsize;
}

复制代码

2.时间复杂度应该是O(n^2)吧？（for嵌套）
3.

#include <memory.h>
//这个也没有调试过，或许有bug，请指出，谢谢！
int arr(int* array,int size)
{
int rsize = 0;
int flag = 0;//前不相等，置1
int i = 0;
for(i = 0;i < size;i++)
{
if(i < size - 1)
if(array[i+1] != array[i])//后面的没有重复
{
rsize++;
flag = 0;
}
}
return rsize;
}

复制代码

一个for，时间复杂度是O(n)。

Kitty喜欢小鱼干 · 发表于 2018-8-13 17:01:49

ZKD 发表于 2018-8-13 16:04
str2set是没有排序的数组变成集合的函数，需要两层嵌套循环，所以时间复杂度是O(N^2)。

而至于str2s ...

感谢您的帮助！结果正是我需要的，只是在看代码的过程中，不太明白temp[]这个数组的功能，还请解释一下。谢谢！

ZKD · 发表于 2018-8-14 10:20:12

Kitty喜欢小鱼干发表于 2018-8-13 17:01
感谢您的帮助！结果正是我需要的，只是在看代码的过程中，不太明白temp[]这个数组的功能，还请解 ...

1、你在检查数组当中重复数字的时候需要将那些第一次出现的数字拷贝到一个新的容器当中，然后在这个新的容器不断对原有数组当中的数字进行检查看是否有重复。而temp数组可以充当这个容器的，temp数组的长度就是删除完重复数字的长度。
2、当你想要检查删除完重复数字的数组究竟是什么的时候，temp数组由于存放着删除完重复数字的结果，也可以给你提供一个参考(直接访问temp就可以)

Kitty喜欢小鱼干 · 发表于 2018-8-14 12:10:47

ZKD 发表于 2018-8-14 10:20
1、你在检查数组当中重复数字的时候需要将那些第一次出现的数字拷贝到一个新的容器当中，然后在这个新的 ...

好的，理解。谢谢！

账号		自动登录	找回密码
密码			立即注册