posts - 73, comments - 55, trackbacks - 0

java整型數組平衡點算法

/*

?*?整形數組平衡點問題：平衡點指左邊的整數和等于右邊的整數和，

?*?求出平衡點位置，要求輸入的數組可能是GB級

?*?

?*?本題要求找出整型數組的一個平衡點（如果要找出所有平衡點的話，按此方法需要把每一個平衡點都存起來）

? */

public ? class ?Test? {

???? public ? int ?findBalanceableNod( int []?a) {

???????? if (a? == ? null ) {

???????????? return ? - 1 ;

????????}

???????? long ?sum? = ? 0l ;

???????? long ?subSum? = ? 0l ;

???????? for ( int ?i? = ? 0 ;?i? < ?a.length;?i ++ ) {

????????????sum? += ?a[i];

????????}

???????? for ( int ?i? = ? 0 ;?i? < ?a.length;?i ++ ) {

???????????? if (subSum? == ?sum? - ?subSum? - ?a[i]) {

???????????????? return ?i;

????????????} else {

????????????????subSum? += ?a[i];

????????????}

????????}

???????? return ? - 1 ;

????}

????

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

???????? // 測試用例：平衡點為0位，為n-1位，為中間位，a的每個為存了Integer.MAX_VALUE(所以用sum,subSum用long型)

???????? int []?a? = ? { - 1 } ;

????????Test?t? = ? new ?Test();

????????System.out.println(t.findBalanceableNod(a));

????}

}

posted on 2007-03-05 10:40 保爾任閱讀(1164) 評論(0) 編輯收藏所屬分類: Arithmetic & Data Structure

新用戶注冊刷新評論列表


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




網站導航: 博客園 IT新聞 Chat2DB C++博客博問管理
相關文章: 求兩個數或多個數的最大公約數算法及其實現組合數學－Catalan數 java用字節數截取字符串 java兩個字符串的最大公共自串字符串匹配 java整型數組平衡點算法 java字符串全排列問題（經典）動態規劃算法二叉樹如何求素數

<

2007年3月

>

日

一

二

三

四

五

六

25

26

27

28

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

7

常用鏈接

留言簿(4)

隨筆分類

隨筆檔案

文章分類

文章檔案

搜索

最新評論

閱讀排行榜

評論排行榜