Find Max Slice Of Array | Javascript

问题:

I need to find the maximum slice of the array which contains no more than two different numbers.

Here is my array [1, 1, 1, 2, 2, 2, 1, 1, 2, 2, 6, 2, 1, 8]

My thought process on this is to find the numbers that are not repeated and return their index within a new array.

Here is what I have so far:

function goThroughInteger(number) {
    var array = [];
    //iterate the array and check if number is not repeated   
  number.filter(function (element, index, number) {
    if(element != number[index-1] && element != number[index+1]) {
        array.push(index);
      return element;
    }
  })

    console.log(array);
}
goThroughInteger([1, 1, 1, 2, 2, 2, 1, 1, 2, 2, 6, 2, 1, 8]);

I'm unsure where to go next, I'm struggling to understand the question that being - find the maximum slice which contains no more than two different numbers - that confuses me.

回答1:

A solution with a single loop, which checks the last values and increments a counter.

function getLongestSlice(array) {
    var count = 0,
        max = 0,
        temp = [];

    array.forEach(function (a) {
        var last = temp[temp.length - 1];

        if (temp.length < 2 || temp[0].value === a || temp[1].value === a) {
            ++count;
        } else {
            count = last.count + 1;
        }
        if (last && last.value === a) {
            last.count++;
        } else {
            temp.push({ value: a, count: 1 });
            temp = temp.slice(-2);
        }
        if (count > max) {
            max = count;
        }
    });
    return max;
}

console.log(getLongestSlice([58, 800, 0, 0, 0, 356, 8988, 1, 1]));        //  4
console.log(getLongestSlice([58, 800, 0, 0, 0, 356, 356, 8988, 1, 1]));   //  5
console.log(getLongestSlice([1, 1, 1, 2, 2, 2, 1, 1, 2, 2, 6, 2, 1, 8])); // 10

回答2:

 function goThroughInteger(array) {  
   var solutionArray = [];
   var max = 0;
    for (var i = 0; i <= array.length; i++) {
       for (var j = i + 1; j <= array.length; j++) {
         var currentSlice= array.slice(i,j);
         var uniqSet = [...new Set(currentSlice)];
      if(uniqSet.length <3) {
        if(currentSlice.length>max) {
        max= currentSlice.length;
        }
      }
     }      
  }
 console.log(max);
}

goThroughInteger([1, 1, 1, 2, 2, 2, 1, 1, 2, 2, 6, 2, 1, 8]);

This solution checks every possible slice of the array, checks if it has not more than 2 different numbers and finally prints out the length of the longest slice.

回答3:

This is a possible solution, with complexity O(n²) (as pointed out by @le_m in the comments)

goThroughInteger = (list) => {
  let scores = list.reduce((slices, num, pos) => {
let valid = [num];
let count = 0;
for (let i = pos; i < list.length; i++) {
  if (valid.indexOf(list[i]) == -1) {
    if (valid.length < 2) {
      valid.push(list[i]);
      count++;
    } else {
      break;
    }
  } else {
    count++;
  }
}
slices[pos] = { pos, count };
return slices;
  }, []);

  scores.sort((a, b) => b.count - a.count);
  let max = scores[0];
  return list.slice(max.pos, max.pos + max.count);
};

console.log(goThroughInteger([1, 1, 1, 2, 2, 2, 1, 1, 2, 2, 6, 2, 1, 8]));
console.log(goThroughInteger([58, 800, 0, 0, 0, 356, 8988, 1, 1]));
```

The solution calculates the 'score' at every position of the input list, counting the length of a sequence of no more than 2 different values, then takes the result with the highest score and extracts a slice from the original list based on that information.

It can definitely be cleaned and optimized but I think it's a good starting point.