阅微客栈

注册或登录 (丢失密码?):

用户名：
密码：

记住我

阅微客栈 » 头脑风暴

1. 

   zhang
   神

   数组中元素有正有负，如何求元素和最接近于0的子数组

   发布于 9 月 之前 #
2. 

   Wanting
   Member

   o(n^2)的作法，不知有没有更好的..

   void findLeastAbsSumSubArray(int input[], int count) {
   if ((input == NULL) || (count == 0)) return;
   int* sum = new int[count];
   int leastSoFar = abs(input[0]);
   int leastStartIndex = 0;
   int leastEndIndex = 0;
   sum[0] = input[0];
   for (int i = 1; i < count; i++) {
   int leastEndingHere = abs(input[i]);
   sum[i] = 0;
   int leastEndingHereStartIndex = i;
   for (int j = 0; j <= i; j++) {
   sum[j] += input[i];
   if (abs(sum[j]) < leastEndingHere) {
   leastEndingHere = abs(sum[j]);
   leastEndingHereStartIndex = j;
   }
   }
   if (leastSoFar > leastEndingHere) {
   leastSoFar = leastEndingHere;
   leastStartIndex = leastEndingHereStartIndex;
   leastEndIndex = i;
   }
   }
   printf("leastSoFar: %i\nleastStartIndex: %i\nleastEndIndex: %i\n", leastSoFar, leastStartIndex, leastEndIndex);
   delete sum;
   }

   发布于 7 月 之前 #
3. 

   szuxjq
   Member

   to Wanting

   老兄你blabla写这么多代码，看晕眼啊。写个算法描述和复杂度出来就得了嘛。对于一维数组，显然有线性复杂度的解法。对于二维数组，别的帖子有讨论。

   发布于 7 月 之前 #
4. 

   lemonutzf
   Member

   转化成全连通有向图，再用floyd算法（判定条件改成abs最小)，注意排除回路。 时间复杂度应该是O(n^3). Wanting的算法没仔细看。 不过，感觉这个问题不大可能有O(n^2)的解

   发布于 7 月 之前 #

该主题的 RSS Feed

回复

你必须 登录 后发帖。