找到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]

这是我的数组[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.

我不确定下一步该去哪里,我很难理解存在的问题 - 找到包含不超过两个不同数字的最大切片 - 这让我很困惑。

3 个解决方案

#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.

此解决方案检查阵列的每个可能切片,检查它是否具有不超过2个不同的数字,最后打印出最长切片的长度。

#3

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

这是一个可能的解决方案,复杂度为O(n²)(如评论中的@le_m所指出)

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]))

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

它计算输入列表的每个位置的“得分”,计算不超过2个不同值的序列的长度。比较获得最高分的结果,并根据该信息从原始列表中提取切片。

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

它绝对可以清理和优化,但我认为这是一个很好的起点。

#1