亚洲一区精品视频,亚洲视频999,国产亚洲一区在线播放

馬賽克的冬天

編寫人生的代碼

迅雷筆試題(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>
11

using namespace std;
12

int sort(int data[],int n);
13

int 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

}
23

int 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 閱讀(5249) 評論(16) 編輯收藏引用

博主的方法也能正確排序，不過時間復雜度肯定不是O(N)。2層循環有點多余，就是不停的把第一個值放到它自己合適的位置上，Ｎ次可以完成。當然１樓是最直接的方式，不過出題者會不會說這不是我的出題意圖，哈哈。回復更多評論

# 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 博問 Chat2DB 管理

<

2010年9月

>

日

一

二

三

四

五

六

29

30

31

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

1

2

3

4

5

6

7

8

9

統計

隨筆 - 8
文章 - 0
評論 - 23
引用 - 0

公告

QQ:306334649 本博客所發代碼皆為作者原創，大家可以隨便使用。

常用鏈接

留言簿(1)

隨筆檔案

文章分類

C++ (rss)

我的博客

大巴博客
大巴博客，包含搞笑，人生，哲理，雜談，摘錄。歡迎訪問：shexinwei.blogbus.com
搜狐博客
搜狐博客，現在開始不再更新

# re: 迅雷筆試題(C++)[未登錄] 2010-09-25 23:50 bill gates

# re: 迅雷筆試題(C++)[未登錄] 2010-09-25 23:51 Eric

# re: 迅雷筆試題(C++) 2010-09-26 00:26 馬賽克007

# re: 迅雷筆試題(C++)[未登錄] 2010-09-26 09:21 expter

# re: 迅雷筆試題(C++) 2010-09-26 09:38 sponge

# re: 迅雷筆試題(C++) 2010-09-26 10:18 匿名