马赛克007欢迎你

htt://shexinwei.blogbus.com

http://www.cppblog.com/shexinwei

感谢大家的支持

迅雷笔试题(C++)

 1/////////////////////////////////////////////////
 2//迅雷笔试题:
 3//有N个大小不等的自然数(1--N),请将它们由小到大排序。   
 4//要求程序算法:时间复杂度为O(n),空间复杂度为O(1)。
 5
 6#define TEST_XUNLEI
 7
 8#ifdef TEST_XUNLEI
 9
10#include <iostream>
11using namespace std;
12int sort(int data[],int n);
13int main()
14{
15    int data[] = {8,7,9,4,6,5,3,2,1};
16    for(int i = 0 ;i < sizeof(data)/sizeof(int);i++)
17        cout<<data[i]<<" ";
18    cout<<endl;
19    sort(data,sizeof(data)/sizeof(int));
20    system("pause");
21    return 1;
22}

23int sort(int data[],int n)
24{
25    //保证空间复杂度为O(1)
26    int tmp = 0;               
27    for(int i = 0;i < n;i++)    
28    {
29       //移动,直到第data[i]为i+1的时,while结束循环。向后继续判断
30        while(data[i] != i+1)   
31        
32            //每次循环保证了data[i-1]的正确。总共有n个所以时间复杂度为O(N)
33            tmp = data[data[i]-1];
34            data[data[i]-1= data[i];        
35            data[i] = tmp;
36        }

37    }

38    for(int i = 0;i < n;i++)
39        cout<<data[i]<<" ";
40    cout<<endl;
41    return 1;
42}

43
44
45#endif
该题的重点在于,N个1--N的数。

posted on 2010-09-25 22:49 马赛克007 阅读(5128) 评论(16)  编辑 收藏 引用

评论

# re: 迅雷笔试题(C++)[未登录] 2010-09-25 23:50 bill gates

这道题弱智。
你的做法不是O(n)的,你内层while循环不是 O(1)

由于N个数已知是 1 - N

所以,排序后的结果一定是

for (int i = 0; i < N; i++)
data[i] = i+1;

所以,和初始输入无关,而且不需要临时存储空间。  回复  更多评论   

# re: 迅雷笔试题(C++)[未登录] 2010-09-25 23:51 Eric

其实题目都说了是‘有N个大小不等的自然数(1--N)’,还要‘小到大排序’,那只有一种情况就是从1递增到N,所以可以不管原来如何直接输出1-N就行了  回复  更多评论   

# re: 迅雷笔试题(C++) 2010-09-26 00:26 马赛克007

@bill gates
我的达到要求了。
关键问题是如果题目是:有n个数,都是取自1--N(n<N)时候,该如何排序了?
  回复  更多评论   

# re: 迅雷笔试题(C++)[未登录] 2010-09-26 09:21 expter

@马赛克007
你的代码不是O(N),根据题意,明显是一个技巧题
你有一个while循环做数据交换,其实就是一个for而已

答案1,2楼已经说明。
  回复  更多评论   

# re: 迅雷笔试题(C++) 2010-09-26 09:38 sponge

这道题真的好弱智阿 华为笔试也出了这个题目  回复  更多评论   

# re: 迅雷笔试题(C++) 2010-09-26 10:18 匿名

博主的方法也能正确排序,不过时间复杂度肯定不是O(N)。2层循环有点多余,就是不停的把第一个值放到它自己合适的位置上,N次可以完成。当然1楼是最直接的方式,不过出题者会不会说这不是我的出题意图,哈哈。  回复  更多评论   

# re: 迅雷笔试题(C++)[未登录] 2010-09-26 12:44 randyZ

呃,一个简单的置换。。  回复  更多评论   

# re: 迅雷笔试题(C++) 2010-09-26 14:30 Niino

我在CSDN上也看过这道题的讨论,结果就是
for(int i = 0;i < N; ++i)
{
data[i] = i+1;
}
...
感觉有点像脑筋急转弯  回复  更多评论   

# re: 迅雷笔试题(C++) 2010-09-26 20:04 楚天清秋

汗一把,直接
for(int i = 0;i < N; ++i)
a[i] = i+1;

结束了  回复  更多评论   

# re: 迅雷笔试题(C++)[未登录] 2010-09-26 21:55 Eric

@马赛克007
你说“我的达到要求了。关键问题是如果题目是:有n个数,都是取自1--N(n<N)时候,该如何排序了? ”
关键是如果题目是这样,你的程序就错了,还是失败。  回复  更多评论   

# re: 迅雷笔试题(C++) 2010-09-27 19:55 马赛克007

@Eric
那肯定了,我的程序是针对迅雷这个题目的。
我说如果,题目是:有n个数,都是取自1--N(n<N)时候,该如何排序了?不是说我这个程序是针对这个题目的。
  回复  更多评论   

# re: 迅雷笔试题(C++) 2010-09-29 03:55 阿二

迅雷还是这么无聊 校招好玩么  回复  更多评论   

# re: 迅雷笔试题(C++) 2010-10-03 09:54 gifty

@马赛克007
题目是:有n个数,都是取自1--N(n<N)时候,该如何排序了?
如果n个数不同的话,用位排序时间复杂度O(N),空间复杂度O(N)是最好的了!
你的解法明显没达到题目要求,你应该谦虚一点,好好看看前面的人的说法!你要是在学大学生的话看看《编程珠玑》吧!一定会有一种醍醐灌顶的感觉!  回复  更多评论   

# re: 迅雷笔试题(C++) 2010-10-05 23:45 马赛克007

@gifty
谢谢!肯定找个时间看看。  回复  更多评论   

# re: 迅雷笔试题(C++)[未登录] 2011-02-28 22:31 me

2题,无聊
  回复  更多评论   

# re: 迅雷笔试题(C++) 2012-02-27 14:30 E7

@匿名
博主的时间复杂度确实是O(N)的  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2010年9月>
2930311234
567891011
12131415161718
19202122232425
262728293012
3456789

导航

统计

公告

QQ:306334649 本博客所发代码皆为作者原创,大家可以随便使用。

常用链接

留言簿(1)

随笔档案

文章分类

我的博客

搜索

最新评论

阅读排行榜

评论排行榜