亚洲一区二区在线看,久久午夜色播影院免费高清,av成人免费观看

馬賽克的冬天

編寫人生的代碼

迅雷筆試題(C++)

1

/////////////////////////////////////////////////
2

//迅雷筆試題：
3

//有N個大小不等的自然數(shù)（1--N），請將它們由小到大排序。
4

//要求程序算法：時間復(fù)雜度為O(n)，空間復(fù)雜度為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

//保證空間復(fù)雜度為O(1)
26

int tmp = 0;
27

for(int i = 0;i < n;i++)
28

{
29

//移動，直到第data[i]為i+1的時,while結(jié)束循環(huán)。向后繼續(xù)判斷
30

while(data[i] != i+1)
31

{
32

//每次循環(huán)保證了data[i-1]的正確。總共有n個所以時間復(fù)雜度為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的數(shù)。

posted on 2010-09-25 22:49 馬賽克007 閱讀(5238) 評論(16) 編輯收藏引用

這道題弱智。
你的做法不是O(n)的，你內(nèi)層while循環(huán)不是 O(1)

由于N個數(shù)已知是 1 - N

所以，排序后的結(jié)果一定是

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

所以，和初始輸入無關(guān)，而且不需要臨時存儲空間。回復(fù) 更多評論

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

其實題目都說了是‘有N個大小不等的自然數(shù)（1--N）’，還要‘小到大排序’，那只有一種情況就是從1遞增到N，所以可以不管原來如何直接輸出1-N就行了回復(fù) 更多評論

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

@bill gates
我的達(dá)到要求了。
關(guān)鍵問題是如果題目是：有n個數(shù)，都是取自1--N(n<N)時候，該如何排序了？
回復(fù) 更多評論

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

@馬賽克007
你的代碼不是O(N),根據(jù)題意，明顯是一個技巧題
你有一個while循環(huán)做數(shù)據(jù)交換，其實就是一個for而已

答案1，2樓已經(jīng)說明。
回復(fù) 更多評論

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

這道題真的好弱智阿華為筆試也出了這個題目回復(fù) 更多評論

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

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

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

呃，一個簡單的置換。。回復(fù) 更多評論

# re: 迅雷筆試題(C++) 2010-09-26 14:30 Niino

我在CSDN上也看過這道題的討論,結(jié)果就是
for(int i = 0;i < N; ++i)
{
data[i] = i+1;
}
...
感覺有點像腦筋急轉(zhuǎn)彎回復(fù) 更多評論

# re: 迅雷筆試題(C++) 2010-09-26 20:04 楚天清秋

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

結(jié)束了回復(fù) 更多評論

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

@馬賽克007
你說“我的達(dá)到要求了。關(guān)鍵問題是如果題目是：有n個數(shù)，都是取自1--N(n<N)時候，該如何排序了？ ”
關(guān)鍵是如果題目是這樣，你的程序就錯了，還是失敗。回復(fù) 更多評論

# re: 迅雷筆試題(C++) 2010-09-27 19:55 馬賽克007

@Eric
那肯定了，我的程序是針對迅雷這個題目的。
我說如果，題目是：有n個數(shù)，都是取自1--N(n<N)時候，該如何排序了？不是說我這個程序是針對這個題目的。
回復(fù) 更多評論

# re: 迅雷筆試題(C++) 2010-09-29 03:55 阿二

迅雷還是這么無聊校招好玩么回復(fù) 更多評論

# re: 迅雷筆試題(C++) 2010-10-03 09:54 gifty

@馬賽克007
題目是：有n個數(shù)，都是取自1--N(n<N)時候，該如何排序了？
如果n個數(shù)不同的話，用位排序時間復(fù)雜度O(N)，空間復(fù)雜度O(N)是最好的了！
你的解法明顯沒達(dá)到題目要求，你應(yīng)該謙虛一點，好好看看前面的人的說法！你要是在學(xué)大學(xué)生的話看看《編程珠璣》吧！一定會有一種醍醐灌頂?shù)母杏X！回復(fù) 更多評論

# re: 迅雷筆試題(C++) 2010-10-05 23:45 馬賽克007

@gifty
謝謝！肯定找個時間看看。回復(fù) 更多評論

# re: 迅雷筆試題(C++)[未登錄] 2011-02-28 22:31 me

2題，無聊
回復(fù) 更多評論

# re: 迅雷筆試題(C++) 2012-02-27 14:30 E7

@匿名
博主的時間復(fù)雜度確實是O(N)的回復(fù) 更多評論

刷新評論列表

只有注冊用戶登錄后才能發(fā)表評論。
【推薦】100%開源！大型工業(yè)跨平臺軟件C++源碼提供，建模，組態(tài)！



網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

<

2010年10月

>

日

一

二

三

四

五

六

26

27

28

29

30

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

31

1

2

3

4

5

6

導(dǎo)航

統(tǒng)計

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

公告

QQ:306334649 本博客所發(fā)代碼皆為作者原創(chuàng)，大家可以隨便使用。

常用鏈接

留言簿(1)

隨筆檔案

文章分類

C++ (rss)

我的博客

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

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