数组平均分割算法
2017-12-18 本文已影响0人
928e93967d0f
题目
题目1
将一个长度为n(n>0)的整型数组分割成两个数组,要求这两个数组的和之差最小
题目2
任意交换两个长度都为为n(n>0)的整型数组的元素,要求最终这两个数组的和之差最
问题分析
对于第二个问题,我们可以将两个数组合成一个长度为2n的数组,变成类似问题1的数组分隔问题。但它多了一个要求:分割后的两个数组长度都为n。
针对这种分割问题,我们可以采用二叉树的思路(TODO后续补图)
- 对于一个长度为n(n>0)的数组任意分割(题目1)可能的情况为O(pow(2, n-1))。
- 对于一个长度为2n(n>0)的数组平均分割(题目2)可能的情况为O(combinations(list_, n))。
代码实现
题目1
def depart_list(list_):
_size = len(list_)
_av = sum(list_)/2
print('average:{}'.format(_av))
_min = _av
_min_seq = 0
for i in range(0, pow(2, _size - 1)):
_total = 0
for j in range(0, _size):
_total += list_[j]*((i>>j)&1)
if abs(_total - _av) < _min:
_min = abs(_total - _av)
_min_seq = i
print(_total)
print(_min)
print(_min_seq)
_ret = []
for k in range(0, _size):
if _min_seq & (1<<k):
_ret.append(list_[k])
return _ret
depart_list([1231,35,46,6667,235,2563])
### [6667]
题目2:
def av_depart_list(list_):
_size = len(list_)
if _size % 2 != 0:
return None
_size_ret = _size/2
_av = sum(list_)/2
print("average:{}".format(_av))
_min = _av
_min_seq = 0
for i in range(0, pow(2, _size - 1)):
if bin(i)[2:].count('1') != _size_ret:
continue
_total = 0
for j in range(0, _size):
_total += list_[j]*((i>>j)&1)
if abs(_total - _av) < _min:
_min = abs(_total - _av)
_min_seq = i
print(_min)
print(_min_seq)
_ret = []
for k in range(0, _size):
if _min_seq & (1<<k):
_ret.append(list_[k])
return _ret
av_depart_list([1231,35,46,6667,235,2563])
### [35, 46, 6667]