算法-一个整型数组,正负数都有,求这个数组的一个子数组,要求和最接近0

算法-一个整型数组,正负数都有,求这个数组的一个子数组,要求和最接近0

晚风撩人 发布于 2017-01-27 字数 70 浏览 1204 回复 8

一个整型数组,正负数都有,求这个数组的一个子数组,要求和最接近0

如果你对这篇文章有疑问,欢迎到本站 社区 发帖提问或使用手Q扫描下方二维码加群参与讨论,获取更多帮助。

扫码加入群聊

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(8

浮生未歇 2017-10-28 8 楼

这是个经典问题了。所谓经典问题就是已经有一个成套路的解法,然后大家觉得这个大约是最佳的了。
1. 首先将所有元素按绝对值从大到小排序(据信有利于剪枝)
2. 计算出最右边K个数中,所有正数的和,和所有负数的和,记作V+[K], V-[K]
3. 取最小的正数、最大的负数、两者之和中绝对值最小的一个作为剪枝边界M
4. 从左到右递归穷举或递推生成所有的解。如果当前的数值R + V+[K] < -M, 或者R + V-[K] > M,那么当前这个部分和已经没有前途了,剪枝剪掉

采用递归还是递推视问题规模。递推要快一些,占用内存也多一些。
C#代码:

int MinAbs(int[] values)
{
//按绝对值排序,语法看不懂可以不管,反正是那个意思
Array.Sort(values, (x,y)=>(Math.Abs(x) < Math.Abs(y) ? -1 : (Math.Abs(x) > Math.Abs(y) ? 1 : 0)));
int currMinAbs = Math.Abs(values[values.Length - 1]);
int[] SumNeg = new int[values.Length];
int[] SumPos = new int[values.Length];
SumNeg[0] = SumPos[0] = 0;
for(int i = 1; i < values.Length; i++)
{
int tmp = values[values.Length - i];
if(tmp < 0)
{
SumPos[i] = SumPos[i - 1];
SumNeg[i] = SumNeg[i - 1] + tmp;
}
else
{
SumPos[i] = SumPos[i - 1] + tmp;
SumNeg[i] = SumNeg[i - 1];
}
if(Math.Abs(values[values.Length - i - 1] + values[values.Length - i]) < currMinAbs)
{
currMinAbs = Math.Abs(values[values.Length - i - 1] + values[values.Length - i]);
}
}
SortedSet<int>[] allResult = new SortedSet<int>[values.Length];
allResult[0] = new SortedSet<int>();
if(values[0] + SumPos[values.Length - 1] > -currMinAbs && values[0] + SumNeg[values.Length - 1] < currMinAbs)
allResult[0].Add(values[0]);
for(int i = 1; i < values.Length; i++)
{
allResult[i] = new SortedSet<int>();
if(values[i] + SumPos[values.Length - 1 - i] > -currMinAbs && values[i] + SumNeg[values.Length - 1 - i] < currMinAbs)
{
allResult[i].Add(values[i]);
}
foreach(var v in allResult[i - 1])
{
if(values[i] + v + SumPos[values.Length - 1 - i] > -currMinAbs && values[i] + v + SumNeg[values.Length - 1 - i] < currMinAbs)
{
allResult[i].Add(values[i] + v);
if(currMinAbs > Math.Abs(values[i] + v))
{
currMinAbs = Math.Abs(values[i] + v);
}
}
}
}
return currMinAbs;
}

需要返回结果的话差别也不大

想挽留 2017-10-21 7 楼

先计算所有的sum0-j,其中 0<= j <n,然后对sum[0-j]的数组进行排序,那么对于任何i,j段的和等于:

sum[i-j]= sum[0-j] - sum[0-i];

由于已经对sum[0-j]进行了排序,所以只要找相邻的比较就可以了,找出绝对值最接近0的sum[0-j]和sum[0-i],那么i+1 到j 即是所求。需要特别注意的一点是,sum的最前面要增加一个初值sum[-1-0] = 0,否则,如果开始的位置从0开始时,就会出现错误。
代码如下:

 具体程序如下:

[cpp] view plaincopy
#include <stdio.h>
template<typename T>
void Swap(T& a, T& b) {
T tmp = a;
a = b;
b = tmp;
}
template<typename T>
int Partition(T array[], int start, int end) {
int j = start - 1;
T last = array[end];
for (int i = start; i < end; ++i) {
if (array[i] < last) {
Swap(array[i], array[j+1]);
j++;
}
}
Swap(array[end], array[j+1]);
return j+1;
}
template<typename T>
void QuickSort(T array[], int start, int end) {
if (start < end) {
int pivot = Partition(array, start, end);
QuickSort(array, start, pivot - 1);
QuickSort(array, pivot + 1, end);
}
}
int Abs(int a) {
return a < 0 ? -1 * a : a;
}
class SumFromStart {
public:
SumFromStart() : end_(0), sum_(0) {}
int end_;
int sum_;
bool operator<(const SumFromStart& right) {
return sum_ < right.sum_;
}
};
bool SubArraySumNearZero(int array[], int length, int* start, int* end) {
if (length < 1) {
return false;
}
if (length == 1) {
*start = 0;
*end = 0;
return true;
}
SumFromStart sum_from_start[length + 1];
sum_from_start[0].sum_ = 0;
sum_from_start[0].end_ = -1;
for (int i = 1; i <= length; ++i) {
sum_from_start[i].sum_ = sum_from_start[i-1].sum_ + array[i-1];
sum_from_start[i].end_ = i - 1;
}
QuickSort(sum_from_start, 0, length + 1);
for (int i = 0; i <= length; ++i) {
printf("%d ", sum_from_start[i].sum_);
}
printf("n");
int min = sum_from_start[1].sum_ - sum_from_start[0].sum_;
for (int i = 2; i < length; ++i) {
if (Abs(sum_from_start[i].sum_ - sum_from_start[i-1].sum_) < min) {
if (sum_from_start[i].end_ < sum_from_start[i-1].end_) {
*start = sum_from_start[i].end_ + 1;
*end = sum_from_start[i-1].end_;
} else {
*start = sum_from_start[i-1].end_ + 1;
*end = sum_from_start[i].end_;
}
}
}
return true;
}
int main(int argc, char** argv) {
int array[] = {-2, 3, 4, -5, 8, 2, -2};
int start = -1;
int end = -1;
SubArraySumNearZero(array, sizeof(array) / sizeof(int), &start, &end);
printf("%d %dn", start, end);
}

参考:http://blog.csdn.net/bertzhang/article/details/7311647
http://blog.csdn.net/kingjinzi_2008/article/details/7690194

夜无邪 2017-10-15 6 楼

如果要求的这个子数组是连续的话,那么可以用 O(n)的时间计算出。
这个问题可以转化为求连续子数组最小和的问题。即子数组之和与0之间的差距最小。
解决方法可以参考 《编程之美》中求解连续子数组最大和问题的解题思路。

int nearestToNum(int arr[],int len, int num)
{
int e = 0;
int sumAll,sumStart;
sumStart = sumAll = arr[e];
while(e < len-1)
{
e ++;
if( abs(num - arr[e]) < abs(num - (arr[e]+sumStart)) )
{
sumStart = arr[e];
}else{
sumStart += arr[e];
}
if( abs(num - sumStart)< abs(num - sumAll) )
{
sumAll = sumStart;
}
}
return sumAll;
}
int main()
{
//...
int nearestToZero = nearestToNum(arr,len,0);
return 0;
}

灵芸 2017-07-28 5 楼

假设sum[i]=a[0]+a[1]+...+a[i];
那么任意一个子数组sum[i-j]=sum[j]-sum[i]
要和最接近0,即是|sum[i-j]|的值最小,可以通过以下算法实现:
1、求出所有的sum[i]
2、对sum数组从小到大排序
3、找出差的绝对值最小的相邻的两个sum[j]和sum[k]
4、a[j]到a[k]即是所要找的子数组

瑾兮 2017-07-13 4 楼

我想到一个思路但是还没实现,采用动态规划思想,先计算1个元素绝对值最小的,保存最小元素,再计算2个元素相加绝对值最小的,保存相加等于最小值的2个元素;再计算3个元素相加绝对值最小的,保存相加等于最小值的3个元素;一次类推,直到n(array.length)个元素相加绝对值最小,保存相加等于最小值的n个元素;最后在计算的1个元素相加和最小的,2个元素相加和最小,3个元素相加和最小,…… ,n(array.length)个元素相加和最小中找个最小值m,则m就是这个就是求和最近进0的,由相加和等于m的元素组成的数组就是所要求的子数组。

归属感 2017-07-11 3 楼

先加一个0进入数列
然后进行排序,接着:
记数列中就会出现N个正数,M个负数
记正数和为N1,负数和的绝对值为M1
如果N1<M1,剔除绝对值比M1大的数
如果M1<N1,剔除绝对值比N1大的数
任意取得正负两个数作为一个集合f(比如取得0左右两边的数),先假设这两个数相加后的绝对值 m最接近0,且记这两个相加后的和为k
如果k是正数,记该负数左右两边的值为a,b,正数或正数集合为m
计算{a}∪f,{b}∪f,{a,m}绝对值记为al,br,a1
判断 al,ar,a1,m 哪个最小

如果al或ar或a1是最小值,那么m=al或ar或a1,f等于所对应的集合
更新k,如果集合中有a值,那么从a的左边开始寻找一个数X,判断{X,m}的绝对值是否小于k
(这么做是防止f中出现跳数较大的情况)
如果有a的集合仍然是正数,则对{a的左值,f}的绝对值与f进行判断,直到不是正数或者到末尾为止
如果有b的集合仍然是正数,则对{b的右值,f}的绝对值与f进行判断,直到不是正数或者到末尾为止
如果al,ar,a1,m 中间有一个数等于0,则等于0的集合就是最接近0的数组

反之,如果是负数,则与正数类似

方法二 镜子法:
正数是负数的对立面,负数是正数的对立面
具体没想好,大致是这样的:
先对数列进行裁剪和排序
所谓镜子法,就是以一组都是负数或者是正数的为标准,去对照另一组数,求的相似度

该数列分为正数和负数两块 以负数为例,

负数的对立面也就是正数区,但这只是一个虚拟区域,需要真实数据去填充
换句话说,就是将负数区域的数的绝对值与正数去比较,在正数区域取得与负数区域绝对值最相似的数
以相似度进行排序
如果取得完全相似的数组则输出
如果没有取得,那以所求得的相似度作为数列(取不到最相似的数则将该数做为一个集合,其相似度即是该数)依照以上方法进行判断,
值得注意的是:此时以相似度排出的数列,已经近似等于数列的1/2,一直做下去就是1/4,1/8,1/16,1/32,1/64........................

而且有些数或者是集合可以通过裁剪的方式进行去除

依照顺序取数也可以,但这样效率是不是比取最相似数的效率高,目前还没有结论

想挽留 2017-03-18 2 楼

可以将这个问题转化为没有重量上限(这里没有上限其实有个最大值,用宏定义下这个最大就行了)的背包问题。

夜无邪 2017-02-24 1 楼

可以用一个数组存储元素 一部分是大于0的 一部分是小于0的 如果有等于0的 那好 不用计算了 取出0就是结果

然后进行划分 首先如果只有负数的多个元素的划分 那么不可能最接近0 因为他们中每个元素都比这样的组合好

例如 123 -23 89 765 -41

然后划分负数部分
1、 -23
2、-41
3、-23 -41
划分正数部分
1、123
2、89

3、765
4、123、89
5、123、765
6、89、765
然后用复数部分与正数部分 分别相加 最接近0的组合 便可以产生了