走在架構(gòu)師的大道上 Jack.Wang's home

Java, C++, linux c, C#.net 技術(shù),軟件架構(gòu),領(lǐng)域建模,IT 項目管理 Dict.CN 在線詞典, 英語學(xué)習(xí), 在線翻譯

BlogJava

管理

195 Posts :: 3 Stories :: 728 Comments :: 0 Trackbacks

微軟面試題---求子數(shù)組最大乘積問題

        給定一個長度為N的整數(shù)數(shù)組，只允許用乘法，計算任意（N-1）個數(shù)的組合乘積中最大的一組，并
寫出算法的時間復(fù)雜度。
       最容易想到的就是通過一次遍歷把所有（N-1）個數(shù)的組合找出來，分別計算他們的乘積，并比較
大小。由于總共有N個（N-1）個數(shù)的組合，總的時間復(fù)雜度為O（N的2次方）,顯然這不是最好的解決
辦法。
       且看下面的實現(xiàn)方法，當(dāng)然也是比較簡單的，畢竟沒太多時間思考，他的時間復(fù)雜度只有O(N)。
       當(dāng)然肯定有其他的方式解決這個問題，blog友如果有好的方式可以貼出來分享。謝謝！

package org.blogjava.arithmetic;
2

import java.util.ArrayList;
4

/**
6

* @author Jack.Wang
7

* @see http://jack2007.blogjava.net/
8

*/
9

public class Array<E> extends ArrayList<E> {
10

private static final long serialVersionUID = 7799621696481440826L;
11

private static long maxOfSubArray(Array arr) {
13

// 最大值
14

long max = 0;
15

int size = arr.size();
16

// s[i]表示前i個元素的乘積,可知s[i]=s[i-1]*arr.get(i-1) 其中(1<=i<=N)
17

long[] s = new long[size + 1];
18

s[0] = 1;
19

// t[i]表示i后面元素的乘積，可知t[i]=t[i+1]*arr.get(i) 其中(1<=i<=N)
20

long[] t = new long[size + 1];
21

t[size] = 1;
22

// 設(shè)p[i]為除第i個元素之外的其他元素之積，即：p[i]=s[i-1]*t[i+1];
23

long[] p = new long[size + 1];
24

// 求出 s數(shù)組
26

for (int i = 1; i <= size; i++) {
27

s[i] = s[i - 1] * ((Integer) arr.get(i - 1));
28

}
29

// 求出t數(shù)組
30

for (int i = size - 1; i >= 0; i--) {
31

t[i] = t[i + 1] * ((Integer) arr.get(i));
32

}
33

// 計算 p數(shù)組
34

for (int i = 1; i <= size; i++) {
35

p[i] = s[i - 1] * t[i];
36

if (p[i] > max) {
37

max = p[i];
38

}
39

}
40

return max;
41

}
42

public static void main(String[] args) {
44

Array<Integer> array = new Array<Integer>();
45

array.add(1);
46

array.add(4);
47

array.add(6);
48

array.add(10);
49

array.add(12);
50

array.add(40);
51

// 上面的數(shù)字很簡單,口算也知道N-1個最大乘積為115200
52

// 算法結(jié)果：
53

System.out.println(" 算法結(jié)果：" + maxOfSubArray(array));
54

}
55

}
57

本博客為學(xué)習(xí)交流用，凡未注明引用的均為本人作品，轉(zhuǎn)載請注明出處，如有版權(quán)問題請及時通知。由于博客時間倉促，錯誤之處敬請諒解，有任何意見可給我留言，愿共同學(xué)習(xí)進步。

posted on 2008-10-17 12:43 Jack.Wang 閱讀(4810) 評論(11) 編輯收藏所屬分類: 數(shù)學(xué)&算法

Feedback

# re: 微軟面試題---求子數(shù)組最大乘積問題 2008-10-17 13:33 wpf

這個，從 n個數(shù)據(jù)中找到最小的一個，剩下的乘積最大，不就行了，當(dāng)然，為正數(shù)的情況下回復(fù) 更多評論

# re: 微軟面試題---求子數(shù)組最大乘積問題 2008-10-17 14:17 Jack.Wang

@wpf
恩是的，可以分為三種情況：正數(shù)，負(fù)數(shù)，和零進行分析，全為正數(shù)時，除去最小的那個，剩下的乘積就是最大的！當(dāng)然其他情況也可進一步分析，也是一個不錯的解決方式。復(fù)雜度也是big O N,等我把這種方式補上！謝謝！回復(fù) 更多評論

# re: 微軟面試題---求子數(shù)組最大乘積問題 2008-10-17 17:00 Eric Jiang

整數(shù)當(dāng)然應(yīng)該不能排除負(fù)數(shù)和零的情況。
把所有數(shù)乘起來，分別再整除每個數(shù)，保留最大的。回復(fù) 更多評論

# re: 微軟面試題---求子數(shù)組最大乘積問題 2008-10-17 17:06 YYX

@Eric Jiang
關(guān)鍵不可能把所有數(shù)乘起來，除非你借用BigDecimal之類的類回復(fù) 更多評論

# re: 微軟面試題---求子數(shù)組最大乘積問題 2008-10-17 17:55 ZelluX

@YYX
n個數(shù)乘起來不可能做到，n-1個數(shù)就可以了？回復(fù) 更多評論

# re: 微軟面試題---求子數(shù)組最大乘積問題 2008-10-17 20:05 Jack.Wang

@YYX
確實存在溢出問題，基本上那種算法都會涉及到多數(shù)相乘，所以用 bigdecimal 表述數(shù)字是需要的！回復(fù) 更多評論

# re: 微軟面試題---求子數(shù)組最大乘積問題 2008-10-17 20:59 小亮Web

難等結(jié)果回復(fù) 更多評論

# re: 微軟面試題---求子數(shù)組最大乘積問題[未登錄] 2008-10-17 22:27 ol_soft

@wpf
同意啊回復(fù) 更多評論

# re: 微軟面試題---求子數(shù)組最大乘積問題 2008-10-18 03:55 ZelluX

其實壓根就不用乘法吧。。。回復(fù) 更多評論

# re: 微軟面試題---求子數(shù)組最大乘積問題 2008-10-18 16:41 wpf

這個是不是沒要求最后乘法的結(jié)果，只要得到n-1分別是那些就好了吧，呵呵
這樣基本上不用考慮溢出的情況回復(fù) 更多評論

# re: 微軟面試題---求子數(shù)組最大乘積問題 2008-10-22 18:28 stonebow

一次遍歷，如果遇到兩個零就不用算了；然后分別記錄最小正數(shù)和最大負(fù)數(shù)和最小負(fù)數(shù)。盡量保證所選數(shù)里有偶數(shù)個負(fù)數(shù)，如果為奇數(shù)個的話就用里面的絕對值最小的負(fù)數(shù)換外面絕對值最大的正數(shù)，或用絕對值最小的正數(shù)換外面絕對值最大的負(fù)數(shù)。只要有一個正數(shù)就沒問題，如果都是負(fù)數(shù)就要看N的奇偶性了。反正一次遍歷總能找到這些數(shù)，然后可以根據(jù)判斷條件得出答案回復(fù) 更多評論

新用戶注冊刷新評論列表


只有注冊用戶登錄后才能發(fā)表評論。




網(wǎng)站導(dǎo)航: 博客園 IT新聞 Chat2DB C++博客博問管理
相關(guān)文章: 計算字符串相似度的簡易算法微軟面試題---階乘問題微軟面試題---求子數(shù)組最大乘積問題微軟面試題---求出1的個數(shù)之小解 Java中對HashMap的深度分析與比較（轉(zhuǎn)載初學(xué)者筆記）為什么HashCode對于對象是如此的重要?

走在架構(gòu)師的大道上 Jack.Wang's home

公告

留言簿(26)

我參與的團隊

隨筆分類(232)

隨筆檔案(190)

我的鄰居們

積分與排名

最新評論

閱讀排行榜

評論排行榜

Feedback