算法笔试题之平衡点问题

Love The Way You Lie 2022-05-18 08:25 140阅读 0赞

## 平衡点问题 ##

**平衡点问题**: 一个数组中的元素，如果其前面的部分等于后面的部分，那么这个点的位序就是平衡点。  
  比如列表numbers = \[1, 3, 5, 7, 8, 25, 4, 20\]，25前面的总和为24，25，后面的总和也是24，那么25就是这个列表的平衡点。  
  要求编写程序，寻找并返回任意一个列表的平衡点。

## 一般算法 ##

假设列表的长度为N，N大于等于3。（因为N=1,2的时候问题无意义）  
  遍历第二个元素至倒数第二个元素，分别计算该元素的左半部分的和与右半部分的和，如果左半部分的和等于右半部分的和，则返回该元素。  
  该算法的优点是想法简单，实现简介，但其时间复杂度为O(n2)  O ( n 2 ) , 效率并不高。

## 优化算法 ##

针对上述算法的缺点，我们在此基础上做改进，使得运算效率能提升。  
  首先我们定义两个变量left\_sum和right\_sum， 其初始值分别为0和该列表第一个元素以后的所有元素的和。遍历第二个元素至倒数第二个元素，每一次遍历，left\_sum加上该元素前的一个元素，right\_sum减去该元素，如果left\_sum等于right\_sum，则返回该元素。  
  该算法是对上述算法的一个优化，使得我们不用在每次遍历元素的时候求取左半部分和右半部分的和，只需要做一次加法和减法即可。具体分析该算法，我们不难求得该算法的时间复杂度为O(n)  O ( n ) ，即线性时间复杂度。  
  接下来我们将会分别给出上述两种算法的Python代码和Java代码，做一些比较。

## Python代码 ##

我们取测试的列表为\[-1, 1\]\*50000+\[1,3,5,7,8,25,4,20\],该列表共100008个元素。  
  完整的Python代码如下：

""" balance point problem """
    import time
    
    # 优化算法
    def balance_point(a):
    
        # 初始值
        left_sum, right_sum = (0, sum(a[1:]))
    
        #下标为1, 2, 3, ..., len(a)-2时的情形
        for i in range(1, len(a)-1):
            left_sum += a[i-1]
            right_sum -= a[i]
            if left_sum == right_sum:
                return i
    
        return -1
    
    # 一般算法
    def balance_point2(a):
    
        # 遍历第2个至倒数第2个元素，分别计算其左半部分和右半部分的和
        # 如果其左半部分和右半部分的和，则返回该下标
        for i in range(1, len(a)-1):
            left_sum = sum(a[:i])    # 左半部分的和
            right_sum = sum(a[i+1:]) # 右半部分的和
            if left_sum == right_sum:
                return i
        return -1
    
    # 测试两种不同算法的消耗时间
    t1 = time.time()
    # 列表a,一共有100008项
    a = [1,-1]*50000+[1,3,5,7,8,25,4,20]
    index = balance_point(a)
    t2 = time.time()
    if(index != -1):
        print("优化算法耗时：%.2f s, index: %d, number: %d."%(t2-t1, index, a[index]))
    a = [1,-1]*50000+[1,3,5,7,8,25,4,20]
    index = balance_point2(a)
    t3 = time.time()
    if(index != -1):
        print("一般算法耗时：%.2f s, index: %d, number: %d."%(t3-t2, index, a[index]))

输出结果如下：

优化算法耗时：0.02 s, index: 100005, number: 25.
    一般算法耗时：105.46 s, index: 100005, number: 25.

## Java代码 ##

完整的Java代码如下：

package Problems;
    
    import java.util.ArrayList;
    import java.util.Date;
    
    // 平衡点问题(balance point problem)
    public class Balance_Point {
        public static void main(String[] args){
    
            // 创建测试数组a
            ArrayList<Integer> a = new ArrayList<>();
            for(int i=0; i<50000; i++) {
                a.add(1); a.add(-1);
            }
            int[] b = {
       1,3,5,7,8,25,4,20};
            for(int i: b) {a.add(i);}
    
            // 测试两种不同算法的消耗时间
            Date t1 =  new Date(); // 开始时间
            int index = balance_point(a);
            Date t2 =  new Date(); // 一般算法结束时间
            Long cost_time1 = t2.getTime()-t1.getTime();
            if(index != -1)
                System.out.println(String.format("一般算法：%d -> %d, 耗时：%.2fs.", index, a.get(index), cost_time1*1.0/1000));
            Date t3 =  new Date(); // 开始时间
            int index_opt = balance_point_opt(a);
            Date t4 =  new Date(); // 优化算法结束时间
            Long cost_time2 = t4.getTime()-t3.getTime();
            if(index != -1)
                System.out.println(String.format("优化算法：%d -> %d, 耗时：%.2fs.", index_opt, a.get(index_opt), cost_time2*1.0/1000));
    
        }
    
        // 一般算法
        public static int balance_point(ArrayList<Integer> a){
    
            /* 遍历第2个至倒数第2个元素，分别计算左半部分和右半部分的和 * 如果左半部分和右半部分的和，则返回该下标 */
            for(int i=1; i<a.size()-1;i++){
                int left_sum = 0; // 左半部分的和
                for(int j=0; j<i; j++)
                    left_sum += a.get(j);
                int right_sum = 0; // 右半部分的和
                for(int k=i+1; k<a.size(); k++)
                    right_sum += a.get(k);
                if(left_sum == right_sum)
                    return i;
            }
    
            return -1;
        }
    
        // 优化算法
        public static int balance_point_opt(ArrayList<Integer> a){
    
            int left_sum = 0;
            int right_sum = 0;
            for(int i=1; i<a.size();i++)
                right_sum += a.get(i);
    
            // 下标为1,2,3,...,a.length-2时的情形
            for(int i=1; i<a.size()-1;i++){
                left_sum += a.get(i-1);
                right_sum -= a.get(i);
                if(left_sum == right_sum)
                    return i;
            }
    
            return -1;
        }
    
    }

运行该Java程序，得到的输出如下：

一般算法：100005 -> 25, 耗时：9.14s.
    优化算法：100005 -> 25, 耗时：0.02s.

从中我们也可以发现，同样的程序，Java的运行时间要远远比Python来得快。  
  本次分享到此结束，如果任何问题，欢迎交流~~

注意：本人现已开通两个微信公众号： 因为Python（微信号为：python\_math）以及轻松学会Python爬虫（微信号为：easy\_web\_scrape）， 欢迎大家关注哦~~