preface

Nuggets team number online, help you Offer impromptu! Click for details

Topic describes

Their thinking

  • So when I do this problem, I first use a double pointer, left and right
  • I stop iterating on the ith element and take the product
  • But it timed out
  • Finally, the problem is solved successfully by means of symmetric traversal

Solution code 1: Violent double pointer (timeout)

var constructArr = function (a) {
    // use the left and right pointer traversal method
    const result = [];
    let l = 0;
    let r = a.length - 1;
    let temp = 1;
    let temp2 = 1;
    for (let i = 0; i < a.length; i++) {

        while(l ! == i) { temp = temp * a[l]; l++; }while(r ! == i) { temp2 = temp2 * a[r]; r--; } l =0;
        r = a.length - 1;
        result.push(temp * temp2)
        temp = 1;
        temp2 = 1;
    }
    return result;
};
Copy the code

Timeout reason

  • With multiple cycles involved, the time complexity is too high and must be improved.

Solution code 2: Truncate all elements except I (timeout)

var constructArr = function (a) {

    const result = [];
    let testarr = [];
    let l = 0;
    let r = a.length - 1;
    let temp = 1;
    let temp2 = 1;
    for (let i = 0; i < a.length; i++) { testarr.push(... a.slice(0,i),... a.slice(i+1))
        result.push(testarr.reduce((pre,cur) = > pre * cur,1));
        testarr = [];
    }
    return result;
};
Copy the code

Timeout reason

  • The time complexity is too high.

Solution code 3: Using symmetric traversal (success AC)

var constructArr = function (a) {

    let right = [];
    let left = [];
    const result = [];
    for (let i = 0; i < a.length; i++) {
        if (i === 0) {
            left[i] = a[0];
            right[i] = a[a.length - 1];
        } else {
            left[i] = left[i-1] * a[i];
            right[i] = right[i-1] * a[a.length-1-i]; }}for (let i = 0; i < a.length; i++) {if (i === a.length - 1) {
            result.push(left[left.length-2]);
            break;
        }
        if (i === 0) {
            result.push(right[right.length-2])}else {
            result.push(right[right.length-1-i-1] * left[i-1])}}return result;
};
Copy the code

conclusion

  • At first glance, the problem is not difficult, and everyone is easy to come up with certain ideas, but the difficulty lies in the time complexity of the problem
  • Only low time complexity can pass
  • So the lesson of this case is that we have symmetric ergodictation
  • The symmetric traversal started here is wrapped the ith element, is not to say to the ith element removed, this is my thinking on the erroneous zone, is I’ve always wanted to start will be the first I elements take out, in fact by symmetric traversal, storage and storage on the left side of the array to the right of the array, at first is finished all traversal, then from the results to get the results we want.
  • The way ahead is so long without ending, yet high and low I’ll search with my will unbending. Come on!