算法笔试题之平衡点问题
平衡点问题
平衡点问题: 一个数组中的元素，如果其前面的部分等于后面的部分，那么这个点的位序就是平衡点。
比如列表numbers = [1, 3, 5, 7, 8, 25, 4, 20]，25前面的总和为24，25，后面的总和也是24，那么25就是这个列表的平衡点。
要求编写程序，寻找并返回任意一个列表的平衡点。
一般算法
假设列表的长度为N，N大于等于3。（因为N=1,2的时候问题无意义）
遍历第二个元素至倒数第二个元素，分别计算该元素的左半部分的和与右半部分的和，如果左半部分的和等于右半部分的和，则返回该元素。
该算法的优点是想法简单，实现简介，但其时间复杂度为$O(n^{2})$, 效率并不高。
优化算法
针对上述算法的缺点，我们在此基础上做改进，使得运算效率能提升。
首先我们定义两个变量left_sum和right_sum， 其初始值分别为0和该列表第一个元素以后的所有元素的和。遍历第二个元素至倒数第二个元素，每一次遍历，left_sum加上该元素前的一个元素，right_sum减去该元素，如果left_sum等于right_sum，则返回该元素。
该算法是对上述算法的一个优化，使得我们不用在每次遍历元素的时候求取左半部分和右半部分的和，只需要做一次加法和减法即可。具体分析该算法，我们不难求得该算法的时间复杂度为$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）， 欢迎大家关注哦~~