日期:2014-05-20  浏览次数:20742 次

求解平衡点问题(数组 集合方面)????????????????
写一个函数,返回给定序列的平衡点(任何一个),如果没有返回-1,假定这个序列可达到非常大。
平衡点就是 左边元素和等于他右边元素和(用数组和集合两种方法实现)----面试时太紧张,没有做出来,望高手指点

------解决方案--------------------
Java code

    static void balancepoint(){
        int[] arr = new int[20];                           //数组
        //初始化
        for(int i = 0;i<arr.length;i++){
            arr[i]=(int)(100*Math.random());
        }
        int   begin = 0;                                   //上标
        int   end   = arr.length-1;                        //下标
        int   begincount =0;                      //记录从上标开始的数组的和
        int   endcount   =0;                        //记录从下标开始的数组的和
        for(int i= 0;i<arr.length;i++){                    //打印数组
            System.out.println("第"+(i+1)+"个元素:"+arr[i]);
        }
        
//        分别从上标和下标开始计算和。当上标等于下标时推出循环。如果begincount>endcount.那么下标减一
//        反之,上标加1
        while(begin!=end){
            if(begincount>endcount){
                endcount+=arr[--end];
            }else{
                begincount+=arr[++begin];
            }
        }
        System.out.println("上标和:"+begincount);                     //打印上标和
        System.out.println("下标和:"+endcount);                       //打印下标和
        System.out.println("平衡点为第"+(begin+1)+"个元素:"+arr[begin]);  //输出
    }

------解决方案--------------------
[code=Java][/code]import java.util.ArrayList;

public class BalancePoint2 {

public static double sum(ArrayList<Integer> src,int startIndex, int endIndex) {
double sum = 0;
for(int i=startIndex; i<endIndex; i++) {
sum += src.get(i);
}
return sum;
}

public static int getBalancePoint(ArrayList<Integer> src) {
double total = BalancePoint2.sum(src, 0, src.size());
for(int i=1; i<src.size()-1; i++) {
double pre = BalancePoint2.sum(src, 0, i);
if( pre == (total - src.get(i)) / 2 ) {
return src.get(i);
}
}
return -1;
}

public static void main(String[] args) {
ArrayList<Integer> src = new ArrayList<Integer>();
src.add(1);
src.add(2);
src.add(3);
src.add(3);
src.add(7);
src.add(9);
src.add(0);
System.out.println(BalancePoint2.getBalancePoint(src));
}

}