加载中…
个人资料
  • 博客等级:
  • 博客积分:
  • 博客访问:
  • 关注人气:
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
正文 字体大小:

转:有个数组a[100]存放了100个数,这100个数取自1-99,且只有两个相同的数,剩下的98个数不同,写一个搜索

(2012-02-09 07:28:08)
标签:

杂谈

题目描述的不是很清晰啊,搜索算法是找出这个数还是找出这个重复数字的两个下标(位置)?
   一,如果仅仅是找出这个数,那么可以这么做:
        int baseSum = (1+99)/2*99;  //1+2+...99
        int sum = 0;
        int i;
        for(i=0; i<100; i++)
        {
            sum += a[i];
        }
        //sum-baseSum即是要搜索的数字
   二,如果需要找出重复数字的下标,可以以空间换取时间的代价:
        int b[100];    //b[i] = x,表示a[x] = i
        memset(b, sizeof(int)*100, -1);
        int i;
        for(i=0; i<100; i++)
        {
            if(-1 == b[a[i]])
            {
                b[a[i]] = i;
            }
            else
            {
                 //说明a[i]这个数曾经出现过,那么a[i]就是重复的数字,
                 //之前保存的下标b[a[i]]和当前的i就是两个下标
            }
        }

 

http://zhidao.baidu.com/question/190187675.html?push=ql

0

阅读 收藏 喜欢 打印举报/Report
  

新浪BLOG意见反馈留言板 欢迎批评指正

新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 产品答疑

新浪公司 版权所有