注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Fly to the Sky!

很多人因为寂寞而错爱一个人,更多人因为错爱一个人而寂寞一生。

 
 
 

日志

 
 

百度面试题(程序实现)  

2008-10-17 14:01:33|  分类: C/C++ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

算法:2n个数,一半奇数,一半偶数,设计一个程序让奇数位上的数是奇数,偶数位上的是偶数,并计算程序的空间复杂度和时间复杂度

写了一个程序: 如下

#include <iostream>
#define N 20
using namespace std;
void exchange( int&x, int&y) //交换函数
{
        int tmp;
        tmp=x;
        x=y;
        y=tmp;
}
int main()
{
        int a[N]={11,55,88,77,1,59,47,22,44,66,57,20,53,99,24,28,11,68,70,80};
        for(int i=0;i<N;i++)
        {
                if( ((i%2==0) && (a[i]%2==0)) || ((i%2==1) && (a[i]%2==1))) //判断:如果奇数位是奇数,偶数位是偶数,则继续循环
                {
                        continue;
                }
                else//如果出现不符合的情况
                {
                        for( int j=i+1;j<N;j++)//向前查找与当前奇数或偶数相符合的数
                        {
                                if( ((i%2)==(a[j]%2)) && ((j%2)!=a[j]%2))//如果找到了与当前位相符合的数,同时判断这个数是否与其当前符合,如果符合,不发生交换(防止多次发生交换),如果不符合,则交换,(这样其实就同时使两个数是正确的位置)
                                {
                                        exchange(a[i],a[j]);
                                        break;
                                }
                                else
                                {
                                        continue;
                                }
                        }
                }
        }
        for(int k=0;k<N;k++)
        {
                cout<<k<<"==="<<a[k]<<endl;
        }
        return 0;

}

时间复杂度,大循环要循环n次,即每个位置都要进行判断。最好的情况下是O(n),最坏情况下,要交换n/2次(因为每次交换可以保证两个位置被交换为正确的情况)。

空间复杂度:只需要n各大小的存储空间。

 

不知道我这个想法是否合适, 希望大家能改进一下 谢谢!

可以交流!

 

  评论这张
 
阅读(1244)| 评论(5)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017