非常简单的问题寻求高手方案 - C语言论坛

已结贴√ 问题点数：100 回复次数：13

非常简单的问题寻求高手方案

比如：

有数组（或者整数序列） int s[]={1,3,2,4,7};

求在序列1-8中有哪个数字被遗漏了

我的输出是：

被遗漏的数据有    5
被遗漏的数据有    6
被遗漏的数据有    8

但是我的代码却是用的比较暴力的枚举办法  很是想知道其他方案

搜索更多相关主题的帖子: 暴力　

第 2 楼

得分:10

你用的枚举法，代码差不多如下吧

程序代码：

#include <stdio.h>
#include <malloc.h>

void foo_bitmark( int a, int b, const int s[], size_t n )
{
    unsigned* mark = calloc( ((b+1-a)+sizeof(unsigned)-1)/sizeof(unsigned), sizeof(unsigned) );
    for( size_t i=0; i!=n; ++i )
        mark[ (s[i]-a)/sizeof(unsigned) ] |= 1u << ( (s[i]-a)%sizeof(unsigned) );

    for( size_t i=a; i!=b+1; ++i )
        if( !(mark[(i-a)/sizeof(unsigned)] & (1u<<((i-a)%sizeof(unsigned)))) )
            printf( " %d", i );
    printf( "\n" );
    free( mark );
}

int main()
{
    int s[] = { 1,3,2,4,7 };
    foo_bitmark( 1, 8, s, sizeof(s)/sizeof(s[0]) );

    return 0;
}

就是用 bit数组记录已有的数字。

【如果不开辟数组的话】
如果只缺一个数，找出这个数很简单，用 sigma(a,b) - sum(s)
即，假如一个数都不少，其和当为 (b+a)*(b-a+1)/2
实际和为 s[0]+s[1]+s[2]+ …… + s[n-1]
两者一减就得到那个缺少的数
（虽然还有其它方法，比如不求和，而是求『异或』结果，但本质相同，下面也不再讲）

如果只缺两个数，设这两个数为x和y，则有
x + y = a到b的和 - s的和
x*x + y*y = a到b的平方和 - s的平方和
求解这个方程就得到x和y

如果只缺三个数，设这两个数为x和y和z，则有
x + y = a到b的和 - s的和
x*x + y*y = a到b的平方和 - s的平方和
x*x*x + y*y*y = a到b的令方和 - s的令方和
求解这个方程就得到x、y和z，但已经很难求了

如果只缺四个数，同理，略

具体缺几个数，可以用 n - (b-a+1) 获知

结论是，如果缺一两个数，可以用解方程的手段；如果缺得多，还是暴力枚举最快，代码也最简单。

第 3 楼

得分:10

太高深了,看不懂,我觉得最简单的就是下面的搞法
int s[]={1,3,2,4,7};  排序完成后变成 int s[]={1,2,3,4,7};
然后用 s[x]-s[x-1]=1或者0  代表没遗漏的    大于1的话 s[x]-s[x-1]-1  为遗漏的数字个数输出就为  s[x]+1 s[x]+2 ..........s[x]+s[x]-s[x-1]-1

int main(){
    sort(a);    这个什么排序的算法  我忘记了
    FindLessNum(a,int min,int max,int arraysize)
}

FindLessNum(int *a,int min,int max,int arraysize)   找遗漏的函数
{
    int icount=0,count;
    int cha;

    cha=a[0]-min-1;                      找a[0]和最小数之间的遗漏
    if(cha>1){
        for(count=0;count<cha;count++)
            printf("%d\n",min+count+1);
    }

    for(;icount<arraysize;icount++){
        cha=a[icount+1]-a[icount]-1;
        if(cha>1){
            for(count=0;count<cha;count++)
            printf("%d\n",min+count+1);
        }
    }

    cha=MAX-a[icount]-1;           找最大的数组元素和最大数之间的遗漏
    if(cha>1){
         for(count=0;count<cha;count++)
            printf("%d\n",min+count+1);
    }

}

解答完毕    给我100分

[ 本帖最后由 zhu224039 于 2014-6-5 13:21 编辑 ]

我要成为嘿嘿的黑客，替天行道

第 4 楼

得分:0

以下是引用rjsp在2014-6-5 12:27:43的发言：

你用的枚举法，代码差不多如下吧
#include <stdio.h>
#include <malloc.h>

void foo_bitmark( int a, int b, const int s[], size_t n )
{
    unsigned* mark = calloc( ((b+1-a)+sizeof(unsigned)-1)/sizeof(unsigned), sizeof(unsigned) );
    for( size_t i=0; i!=n; ++i )
        mark[ (s-a)/sizeof(unsigned) ] |= 1u << ( (s-a)%sizeof(unsigned) );

    for( size_t i=a; i!=b+1; ++i )
        if( !(mark[(i-a)/sizeof(unsigned)] & (1u<<((i-a)%sizeof(unsigned)))) )
            printf( " %d", i );
    printf( "\n" );
    free( mark );
}

int main()
{
    int s[] = { 1,3,2,4,7 };
    foo_bitmark( 1, 8, s, sizeof(s)/sizeof(s[0]) );

    return 0;
}就是用 bit数组记录已有的数字。

【如果不开辟数组的话】
如果只缺一个数，找出这个数很简单，用 sigma(a,b) - sum(s)
即，假如一个数都不少，其和当为 (b+a)*(b-a+1)/2
实际和为 s[0]+s[1]+s[2]+ …… + s[n-1]
两者一减就得到那个缺少的数
（虽然还有其它方法，比如不求和，而是求『异或』结果，但本质相同，下面也不再讲）

如果只缺两个数，设这两个数为x和y，则有
x + y = a到b的和 - s的和
x*x + y*y = a到b的平方和 - s的平方和
求解这个方程就得到x和y

如果只缺三个数，设这两个数为x和y和z，则有
x + y = a到b的和 - s的和
x*x + y*y = a到b的平方和 - s的平方和
x*x*x + y*y*y = a到b的令方和 - s的令方和
求解这个方程就得到x、y和z，但已经很难求了

如果只缺四个数，同理，略

具体缺几个数，可以用 n - (b-a+1) 获知

结论是，如果缺一两个数，可以用解方程的手段；如果缺得多，还是暴力枚举最快，代码也最简单。

有位运算的应用资料吗仅仅知道位运算是咋回事不会实际应用正在研究你的代码中。。。。。。。

另附我的代码如下和你的代码原理根本就不一样

程序代码：

#include<stdio.h>

void cr(int beg,int end,int s[],int slen)
{
    int i,j;
    bool flag=false;
    for(i=beg;i<=end;i++)
    {
        for(j=0;j<slen;j++)
        {
            if(i==s[j]) 
            {
                flag=true;
                break;
            }
        }
        if(flag==false) printf("被遗漏的数据有 %4d  \n",i);
        flag=false;
    }
    printf("\n");
}

int main()
{
    int s[]={1,3,2,4,7};
    cr(1,8,s,5);
    return 0;
}

DO IT YOURSELF !

第 5 楼

得分:10

应该先排序，再输出没有的位复杂度小一些

第 6 楼

得分:10

以下是引用xuechengxu在2014-6-5 14:23:12的发言：

集英服务社专业原创服务机构
QQ-1: 1737140158
QQ-2: 2596652003
电邮: sonoffreedom@

广告？

第 7 楼

得分:10

void main()
{int s[]={1,3,2,4,7}
int a[]={1,2,3,4,5,6,7,8}
int i,j;
for(i=0;i<5;i++)
for(j=0;j<8;j++)
if(s[i]=a[j]) a[j]=0;
printf("被遗漏的数据：\n");
for(i=0;i<8;i++)
if(a[i]!=0) printf("%d\t",a[i]);
putchar('\n');
}
刚学，这个可以么？

第 8 楼

得分:10

回复 5 楼 wp231957

你说的只是简单的是吧，那我把你代码改一下：

程序代码：

#include<stdio.h>
#include <stdlib.h>

void cr(int beg,int end,int s[],int slen)
{
    int i;
    int *a;
    a = (int*)calloc(sizeof(int),(end+1));
  
    for(i=0;i<slen;i++)
        a[s[i]]++;
    for (i = beg; i <= end; i++)
        if(a[i] == 0)
             printf("被遗漏的数据有 %4d  \n",i);
    printf("\n");
    free(a);
}

int main()
{
    int s[]={1,3,2,4,7};
    cr(1,8,s,5);
    return 0;
}

//刚才忘了释放分配的内存了，这习惯可不好。
这问题真是太简单了，这也值100？土豪，我们可以做朋友吗？？

[ 本帖最后由 pangshch 于 2014-6-5 18:07 编辑 ]

第 9 楼

得分:10

简单地想了一下：

申请一个8位的空间（或者n位），用位段进行管理，标志相应位置是否缺失，

因为n=8是已知的，所以只要不断左移判断最高位是否为1即可（是否为负数）输出是否缺失。

没写代码只是想了想~

学习编程，为的是表达自己的思想，而不是被别人的思想所禁锢。要先明白自己想干嘛，而不要先问别人让你干嘛。

Black Cat Hello Tomorrow~

第 10 楼

得分:10

以下是引用xsw07122269在2014-6-5 17:09:16的发言：

void main()
{int s[]={1,3,2,4,7}
int a[]={1,2,3,4,5,6,7,8}
int i,j;
for(i=0;i<5;i++)
for(j=0;j<8;j++)
if(s=a[j]) a[j]=0;
printf("被遗漏的数据：\n");
for(i=0;i<8;i++)
if(a!=0) printf("%d\t",a);
putchar('\n');
}
刚学，这个可以么？

结构不清晰哎
#include <stdio.h>
int main()
{ int s[]={1,3,2,4,7}；
  int a[]={1,2,3,4,5,6,7,8}；
  int i,j;
  for(i=0;i<5;i++)
{for(j=0;j<8;j++)
    {if(s[i]==a[j]) a[j]=0;}
     printf("被遗漏的数据：\n");//输出次数好像有点多
  }
  for(i=0;i<8;i++)
  {if(a!=0) printf("%d\t",a);}
  return 0;
  //putchar('\n');
}
大致是这样吧，我也是初学的，表示上面的除了你这个其余我都看不懂= =||

[ 本帖最后由 wssy213 于 2014-6-6 22:16 编辑 ]

坚持----------------------------------唯一的道路
shit ! ! !