0

我最近解决了一个编码问题。我想出了解决以下问题的方法。

给出了一个由 N 个整数组成的非空零索引数组 A。数组 A 代表磁带上的数字。
任何整数 P，例如 0 < P < N，都会将此磁带分成两个非空部分：A[0]、A[1]、...、A[P - 1] 和 A[P]、A[ P + 1], ..., A[N - 1]。
两部分的差值是：|(A[0] + A[1] + ... + A[P - 1]) - (A[P] + A[P + 1] + .. . + A[N - 1])|
换句话说，它是第一部分的总和与第二部分的总和之间的绝对差。
例如，考虑数组 A，这样：
A[0] = 3
A[1] = 1
A[2] = 2
A[3] = 4
A[4] = 3
我们可以将此磁带分成四个位置：
P = 1、差值 = |3 − 10| = 7
P = 2，差值 = |4 - 9| = 5
P = 3，差值 = |6 - 7| = 1
P = 4，差值 = |10 - 3| = 7

写一个函数：function solution(A);
即，给定一个由 N 个整数组成的非空零索引数组 A，返回可以实现的最小差异。
例如，给定：
A[0] = 3
A[1] = 1
A[2] = 2
A[3] = 4
A[4] = 3
该函数应返回 1，如上所述。
假设：
N是[2..100,000]范围内的整数；
数组 A 的每个元素都是 [−1,000..1,000] 范围内的整数。

复杂度：
预期的最坏情况时间复杂度为 O(N)；
预期的最坏情况空间复杂度为 O(N)，超出输入存储（不计算输入参数所需的存储）。
可以修改输入数组的元素。


以下是我测试解决方案得到的反馈：

正确性：small_range 范围序列，长度 = ~1,000 1.900 s运行时
错误测试程序意外终止
性能：检测到的时间复杂度：O(N * N)

所以我在 1000 左右的范围内遇到了一个运行时错误。最重要的是，我没有得到 O(n)。当我使用嵌套的 for 循环时，我得到了 O(n * n) 。

(1) 如何修复运行时错误？
(2) 如何为同一问题构造 O(n) 算法？有什么建议么？

这是我的解决方案： 

    function solution(A){
        var len = A.length;
        var diff = [];  // Array to store the differences
        var sumLeft = 0;    // Sum of array elements from index 0 to index p - 1
        var sumRight = 0;   // Sum of array elements from index p to index n - 1
        for(var p = 1; p < len; p++){
            sumLeft = 0;
            sumRight = 0;
            // Calculate sumLeft:
            for(var i = 0; i < p; i++){
                sumLeft += A[i];
            }
            // Calculate sumRight:
            for(var j = p; j < len; j++){
                sumRight += A[j];
            }
            // Calculate differences, compute absolute values, and push into diff array:
            diff.push(Math.abs(sumLeft - sumRight));
        }
        // Return the minimum of diff array by sorting it and returning the first element:
        return bubbleSort(diff)[0];
    }

    function bubbleSort(array){
        var len = array.length;
        for(var i = 0; i < len; i++){
            for(var j = i + 1; j < len; j++){
                if(array[i] > array[j]){
                    var temp = array[i];
                    array[i] = array[j];
                    array[j] = temp;
                }
            }
        }
        return array;
    }
4

4 回答 4

0

当您测试 的新值时，您不需要计算向量片段的总和P。如果你计算leftSum和rightSum的两个部分P=(p-1)，当你必须计算它时，P=p你只需要：

  • array[p]从rightSum;中删除 和
  • 添加 array[p]到leftSum.

这两者都是 O(1)。如果你这样做 (n-1) 次，你仍然处于 O(n) 复杂度之下。

希望有帮助。

于 2014-10-07T06:37:13.303 回答
0

让我尝试向您解释如何考虑提高算法的空间和时间复杂度。您清楚地意识到您在哪里使用嵌套 for 循环，它大大增加了迭代，并且还可能导致足够大的输入的运行时错误。

第一步应该是减少操作的冗余。现在您重复计算left和的不同值的总和。你根本不需要那个。我会给你一个关于算法如何流动的例子：rightp

 Array indices -> A [0, 1, 2, 3, ....,p ,p+1, ....n-1] for a size n array

 At any point A[p] would act as a pivot as it breaks the array into two.
 For p = 1, You just take the first element i.e A[0] and the right part of the sum is
 A[1] + A[2] + .... A[n-1]

 Let S1 = A[0] and S2 = A[1] + A[2] + .... A[n-1] for p = 1
 The pivot or the break point here is A[p] i.e A[1]

 Calculate the absolute difference |S1- S2| and store it in a variable min-diff

 For p = 2, 

 S1 will simply be S1 + A[1] i.e the previous value of S1 including the last pivot 

 S2 = S2 - A[1], as we have moved on to the next element. 
 The sum of the remaining elements would not account the element we just crossed.

Formally,

S1 = S1 + A[p-1] and S2 = S2 - A[p-1]

Calculate the new difference i.e |S1 - S2| and just check 
if it is smaller than the value of our variable min-diff. 
If it is, update the value of min-diff with the present difference, 
otherwise move on to the next element.

At any value of p, S1 represents sum of left half, 
S2 represents sum of right half and 
min-diff represents the minium absolute difference till now.

该算法的复杂性

  1. 时间复杂度

    我们计算元素之和的唯一一次是第一次计算 A[1]+...A[n-1]。之后我们就一个一个地遍历数组的元素。

    所以我们遍历数组的元素 max 两次。所以时间复杂度显然是O(N)

  2. 空间复杂度

    我们使用三个额外的变量，即 S1、S2 和 min-diff，通过该算法来累加和并存储最小绝对差以及 p 的值和数组的 n 个元素。

    所以这个算法的空间复杂度又是O(N)

附带说明-尽管您根本不需要对这个问题进行排序，因为您只输出最小差异，但无论何时排序，请不要使用冒泡排序，因为它显然是效率最低的排序方法。你最好使用运行时间为O(NlogN)的合并排序或快速排序

我希望我能够解释自己。试着把它编码成一个简单的函数，应该不会花很长时间。它可能也应该修复运行时错误。

于 2014-10-07T06:52:02.700 回答
0

java代码：O(N)

import java.math.*;

class Solution {

  public int solution(int[] A) {

    long sumright = 0;
    long sumleft = 0;
    long ans;

    for (int i =1;i<A.length;i++)
    {
      sumright += A[i];
    }

    sumleft = A[0];
    ans =Math.abs(sumright+sumleft);

    for (int P=1; P<A.length; P++)
    {
      if (Math.abs(sumleft - sumright)<ans)
      {
        ans = Math.abs(sumleft - sumright);
      }
      sumleft += A[P];
      sumright -=A[P];
    }
  return (int) ans;
}

}

于 2014-10-08T07:32:34.840 回答
0

在没有调试的情况下，此解决方案在 Codility 上的任务得分为 100%（正确性和性能均为 100%）：

function solution(A) {
    var sum_right = 0;

    for (int of A.slice(1)) {
        sum_right += int;
    }

    var sum_left = A[0];
    var diff_of_sums = sum_left - sum_right;
    var lowest_diff = Math.abs(diff_of_sums);
    var diff_new;
    // we assume the length is at least 2
    if (A.length == 2) {
        return lowest_diff;
    }
    for (var int of A.slice(1)) {
        diff_new = Math.abs(sum_left - sum_right);
        if (diff_new < lowest_diff) {
            lowest_diff = diff_new;
        }
        sum_left += int;
        sum_right -= int;
    }
    return lowest_diff;
}

带调试：

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(A) {
    var sum_right = 0;

    for (int of A.slice(1)) {
        sum_right += int;
    }

    var sum_left = A[0];
    var diff_of_sums = sum_left - sum_right;
    // var total = Math.abs(sum_left + sum_right);
    var lowest_diff = Math.abs(diff_of_sums);
    var diff_new;
    // we assume the length is at least 2
    if (A.length == 2) {
        return lowest_diff;
    }
    // console.log("lowest_diff initially:", lowest_diff)
    // var diff_of_sums_new = diff_of_sums;
    // console.log("diff_of_sums initially:", diff_of_sums)
    // console.log("A.slice(1):", A.slice(1))
    for (var int of A.slice(1)) {
        // console.log("lowest_diff", lowest_diff)
        diff_new = Math.abs(sum_left - sum_right);
        if (diff_new < lowest_diff) {
            lowest_diff = diff_new;
        }
        sum_left += int;
        sum_right -= int;
    }
    //           if (Math.abs(sumleft - sumright)<ans)
    //   {
    //     ans = Math.abs(sumleft - sumright);
    //   }
    //   sumleft += A[P];
    //   sumright -=A[P];
    //     // console.log("int === -1:", int === -1);
    //     // diff_of_sums = diff_of_sums_new;
    //     console.log("lowest_diff =", lowest_diff);
    //     // console.log("A[index + 1] =", A[parseInt(index) + 1]);
    //     // console.log("parseInt(index) === 1", parseInt(index) === 1)
    //     diff_of_sums = Math.abs(lowest_diff - 2 * Math.abs(int));
    //     // console.log("diff_of_sums =", diff_of_sums);
    //     // console.log("diff_of_sums = Math.abs(diff_of_sums - 2 * A[index + 1]) = ", diff_of_sums_new);
    //     if (diff_of_sums < lowest_diff) {
    //         lowest_diff = diff_of_sums;
    //         // console.log("lowest_diff = diff_of_sums =", diff_of_sums_new)
    //     } else {
    //         return lowest_diff;
    //     }
    // }
    // console.log("lowest_diff before returning", lowest_diff);
    return lowest_diff;
}
// Note that it's better to use test cases in Codility for this, but I've left here to show some.
// console.log("solution([-1000, 1000])", solution([-1000, 1000]));
// console.log("solution([2, 7, 20, 30, 1])", solution([2, 7, 20, 30, 1])); // sum 60, smallest diff = |29 - 31| = 2
// console.log("solution([-2, -7, -20, -30, -1])", solution([-2, -7, -20, -30, -1])); // sum -60, smallest diff = 2
// console.log("solution([-1, -1]):", solution([-1, -1]));
// console.log("solution([-2, -1]):", solution([-2, -1]));
// console.log("solution([-2, -1, -3]):", solution([-2, -1, -3]));
// console.log("solution([]):", solution([]))

最初我尝试从中途开始，但这使实现更加复杂。这是我在放弃这种方法之前想出的（而且我不会为破解解决方案而烦恼）：

function solution(A) {
    // const sum = A.reduce((partial_sum, a) => partial_sum + a); 
    // console.log(sum);
    var size = A.length;
    if (size % 2 == 0) {
        mid = size/2;
    } else {
        mid = Math.floor(size/2);
    }
    console.log("mid initially", mid);
    var sum1 = A.slice(0, mid).reduce((partial_sum, a) => partial_sum + a);
    // console.log("sum1:",sum1);
    var sum2 = A.slice(mid).reduce((partial_sum, a) => partial_sum + a);
    // console.log("sum2:", sum2);
    var sum_diff = sum1 - sum2;
    // console.log("sum_diff:", sum_diff);
    if (sum_diff === 0) {
        return sum_diff;
    }
    // sum_diff = function() {Math.abs(sum2 - sum1)};
    // sum_diff = sum_diff();
    var lowest_diff = Math.abs(sum_diff);
    var diff_negative = (sum_diff < 0);
    console.log("diff_negative initially:", diff_negative)
    var crossed_over = false;
    var sum_diff_new;
    while (diff_negative) {
        mid++;
        if (mid === size) {
            return lowest_diff;
        }
        // var sum1_new = sum1 + A[mid];
        // var sum2_new = sum2 - A[mid];
        // sum_diff_new = sum1_new - sum2_new = sum1 - sum2 + 2*A[mid] = sum_diff - 2*A[mid];
        sum_diff_new = sum_diff - 2*A[mid];
        diff_negative = (sum_diff_new < 0);
        if (diff_negative = false) {
            crossed_over = true;
            if (lowest_diff <= sum_diff_new) {
                return lowest_diff;
            } else {
                return sum_diff_new;
            }
        }
    }

    while(!diff_negative) {
        mid--;
        if (mid === -1) {
            return lowest_diff;
        }
        // var sum1_new = sum1 - A[mid];
        // var sum2_new = sum2 + A[mid];
        // sum_diff_new = sum1_new - sum2_new = sum1 - sum2 - 2*A[mid] = sum_diff - 2*A[mid];
        console.log("sum_diff:", sum_diff);
        sum_diff_new = sum_diff + 2*A[mid];
        console.log("sum_diff_new:", sum_diff_new);
        diff_negative = (sum_diff_new < 0);
        if (diff_negative = true) {
            crossed_over = true;
            var sum_diff_new_pos = Math.abs(sum_diff_new);
            if (lowest_diff <= sum_diff_new_pos) {
                return lowest_diff;
            } else {
                return sum_diff_new_pos;
            }
        }
    }
}

// Issues: doesn't work e.g. with  [-2, -1, -3] and [-2, -7, -20, -30, -1]
于 2019-02-28T12:07:43.387 回答