Javascript Algorithm Practice Removing Negatives From Array - Stack Overflow

admin管理员组

文章数量:1305754

I am having a hard time wrapping my brain around this one :/

• (Removing Negatives) Given an array X of multiple values (e.g. [-3,5,1,3,2,10]), write a program that removes any negative values in the array. Once your program is done X should be posed of just positive numbers. Do this without creating a temporary array and only using pop method to remove any values in the array.

My thought was to write a loop through the array. If X[i] is negative, start another loop swapping X[j] and X[j+1] until the end of the array. (to preserve the order of the array) then use pop().

When I run the script it looks like the loop is infinite. Also it looks like if there are two negative values in a row the second one may get skipped in the next iteration of i. Is there a simpler way?

var X = [1,-6,-7,8,9];
//test= [1,-7,8,-6,9]
temp = 0

for (i = 0;i<X.length-1;i++){
    if (X[i]<0){
        for (j = i;j<=X.length-1;j++){
            X[j] = temp
            X[j] = X[j+1] 
            X[j+1] = temp
        }
        if(X[X.length-1] < 0){X.pop()}
    }
};
console.log(X);

I am having a hard time wrapping my brain around this one :/

• (Removing Negatives) Given an array X of multiple values (e.g. [-3,5,1,3,2,10]), write a program that removes any negative values in the array. Once your program is done X should be posed of just positive numbers. Do this without creating a temporary array and only using pop method to remove any values in the array.

My thought was to write a loop through the array. If X[i] is negative, start another loop swapping X[j] and X[j+1] until the end of the array. (to preserve the order of the array) then use pop().

When I run the script it looks like the loop is infinite. Also it looks like if there are two negative values in a row the second one may get skipped in the next iteration of i. Is there a simpler way?

var X = [1,-6,-7,8,9];
//test= [1,-7,8,-6,9]
temp = 0

for (i = 0;i<X.length-1;i++){
    if (X[i]<0){
        for (j = i;j<=X.length-1;j++){
            X[j] = temp
            X[j] = X[j+1] 
            X[j+1] = temp
        }
        if(X[X.length-1] < 0){X.pop()}
    }
};
console.log(X);

• javascript
• arrays
• algorithm

Share Improve this question Follow edited Apr 21, 2015 at 18:03 Sam 8391010 silver badges1616 bronze badges asked Apr 21, 2015 at 17:40 Water223Water223 7511 silver badge66 bronze badges 4

• 1 Array.filter – Jonathan Commented Apr 21, 2015 at 17:46
• 1 You mention preserving the order of the array, but why? The description doesn't say anything about preserving order. – James Montagne Commented Apr 21, 2015 at 17:48
• Are you allowed to you Array.splice ? – anu Commented Apr 21, 2015 at 17:55
• You are infinite looping because you have X[j+1] = temp inside your j loop. When j is equal to X.length - 1, this line will add an additional entry into the array, causing it to loop again, again adding and looping and adding... forever – James Montagne Commented Apr 21, 2015 at 18:21

Add a ment  | 

5 Answers 5

Sorted by: Reset to default 6

Very similar to your mentioned approach, except there's no reason to maintain order (unless that is missing from the description). Loop in reverse and when a negative is found, swap it with the last element and pop. If we first pop all negatives off of the end, we know the last element is not negative.

var x = [1, -6, -7, 8, 9, -3];

// strip all negatives off the end
while (x.length && x[x.length - 1] < 0) {
  x.pop();
}

for (var i = x.length - 1; i >= 0; i--) {
  if (x[i] < 0) {
    // replace this element with the last element (guaranteed to be positive)
    x[i] = x[x.length - 1];
    x.pop();
  }
}

document.body.innerHTML = '<pre>' + JSON.stringify(x, null, 4) + '</pre>';

This solution has linear plexity as it only iterates the list once.

Sort the array first so the negative numbers are at the end.
We can sort with a callback that moves the negative numbers to the end.

Then iterate backwards and remove the last indices with pop as long as they are negative.

What we're left with is the positive values.

var X = [-3, 5, 3, 8, 1,-6,-7,8,9];

X.sort(function(a,b) {
    return b - a;
});

for (var i=X.length; i--;) {
    if ( X[i] < 0 ) X.pop();
}

document.body.innerHTML = '<pre>' + JSON.stringify(X, null, 4) + '</pre>';

There are many good answers already. Here's a straightforward filter that doesn't sort the array and uses an auxiliary array index j <= i:

function removeNeg(arr) {
    var j = 0;

    // filter array
    for (var i = 0; i < arr.length; i++) {
        if (arr[i] >= 0) arr[j++] = arr[i];
    }

    // pop excess elements
    while (j < arr.length) arr.pop();
}

This is really the C programmer's approach to James Montagne's answer, which is neater, because it pops as you go.

var x = [1, -6, -7, 8, 9];
var i = 0;
while (i < x.length) {
    if (x[i] < 0) {
        x[i] = x[x.length - 1];
        x.pop();
    } else {
        i++;
    }
}   

just pop, no other methods of Array used

Here's a very simple solution that doesn't require sorting. For every element, shift it, push it if it is not negative. Do this a number of times equivalent to the array size. This can either be done with shift/push or pop/unshift.

var origLen = X.length;

for(var i = 0; i < origLen; i++) {
  var val = X.pop();

  if(val > 0)
     X.unshift(val);
}

本文标签： Javascript Algorithm Practice Removing Negatives From ArrayStack Overflow