admin管理员组

文章数量:1342918

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.

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.

• javascript
• arrays

Share Improve this question Follow edited Mar 14, 2017 at 14:30 Filth asked Mar 14, 2017 at 12:35 FilthFilth 3,2281515 gold badges5555 silver badges8383 bronze badges 14

• 1 Nice effort shown. – evolutionxbox Commented Mar 14, 2017 at 12:37
• @evolutionxbox Thank you – Filth Commented Mar 14, 2017 at 12:37
• btw, filter without using the result of Array#filter makes not really sense. – Nina Scholz Commented Mar 14, 2017 at 12:55
• What should be the output in your example ? – Weedoze Commented Mar 14, 2017 at 12:58
• 3 please define slice. – Nina Scholz Commented Mar 14, 2017 at 13:17

 |  Show 9 more ments

4 Answers 4

Sorted by: Reset to default 6

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

 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.

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

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.

Using the sliding window algorithm in O(n) time:

const arr = [1, 1, 1, 2, 2, 2, 1, 1, 2, 2, 6, 2, 1, 8, 1, 1 ,1 ,1, 8, 1, 1, 8, 8];

const map = {
   length: 0
};

let required = [];
for(start = 0, end = 0; end <= arr.length; ){

if(map.length > 2){
    if(map[arr[start]] === 1){
        delete map[arr[start]];
        map.length --;
    }else{
        map[arr[start]]--;
    };
    start++;

}else{
    if(end - start > required.length){
        required = arr.slice(start, end);
    };

    if(map[arr[end]]){
        map[arr[end]]++;
    }else{
        map[arr[end]] = 1;
        map.length++;
    }
    end++;
}
}

console.log(required);

本文标签： Find Max Slice Of ArrayJavascriptStack Overflow