鱼C论坛

 找回密码
 立即注册
查看: 3296|回复: 5

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

[复制链接]
发表于 2018-8-13 14:17:54 | 显示全部楼层 |阅读模式
10鱼币
2.jpg


最佳答案
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,请您指出。

最佳答案

查看完整内容

str2set是没有排序的数组变成集合的函数,需要两层嵌套循环,所以时间复杂度是O(N^2)。 而至于str2set_forsorted是排序之后的数组变成集合的函数,我默认是从小到大排序了。其实这是一个打擂台找最大值/最小值的问题,一旦有新的最大/最小值就需要将其写入数组当中,并更新长度计数器。 此函数用codeblocks测试过,但是我测试的样本较少,可能对某些数组有bug,请您指出。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 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,请您指出。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 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)。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2018-8-13 17:01:49 | 显示全部楼层
ZKD 发表于 2018-8-13 16:04
str2set是没有排序的数组变成集合的函数,需要两层嵌套循环,所以时间复杂度是O(N^2)。

而至于str2s ...

       感谢您的帮助!结果正是我需要的,只是在看代码的过程中,不太明白temp[]这个数组的功能,还请解释一下。谢谢!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-8-14 10:20:12 | 显示全部楼层
Kitty喜欢小鱼干 发表于 2018-8-13 17:01
感谢您的帮助!结果正是我需要的,只是在看代码的过程中,不太明白temp[]这个数组的功能,还请解 ...

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

使用道具 举报

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

好的,理解。谢谢!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-12-23 08:50

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表