查找数组最大切片| Javascript

Question

我需要找到数组中不超过两个不同数字的最大子序列。

这是我的数组：[1, 1, 1, 2, 2, 2, 1, 1, 2, 2, 6, 2, 1, 8]

我的思路是找到不重复的数字，并返回它们在新数组中的索引。

这是目前我所做的：

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

我不确定接下来该怎么做，我很难理解这个问题 - 找到包含不超过两个不同数字的最大切片 - 这让我感到困惑。

- Filth

---

展现了不错的努力。 - evolutionxbox

@evolutionxbox 谢谢您 - Filth

它不够健壮，需要处理任何数组，例如[58, 800, 0, 0, 0, 356, 8988, 1, 1]，应该返回4。她的返回值是2。 - Filth

我使用的数组示例等于10，因为(0,9)的数组切片是该数组中没有超过两个不同数字的最大切片。第二个数组示例也是如此，预期结果为4。 - Filth

定义“slice”：在编程中，“slice”是一个由数组或字符串的一部分元素组成的新序列。这个新序列被称为切片，它可以用来操作原始序列的一部分内容。 - Nina Scholz

Answer 1

一个只有一个循环的解决方案，它检查最后的值并增加计数器。

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

- Nina Scholz

---

目前为止，唯一的运行时复杂度为O(n)的好解决方案。甚至可以很好地推广到3、4或更多数字的切片。 - le_m

太好了！在 JavaScript 中 count = last.count + 1; 这句话的意思是什么？特别是 last.count。我想在 Swift 中应用它。 - Zhou Haibo

@ChuckZHB，“last = temp[temp.length - 1]”。last是temp中的最后一个元素。 - Nina Scholz

应该添加一行代码 temp[temp.length - 1].count = last.count 将 last.count 赋值给 temp 数组的最后一个元素的 count 属性吗？ last.count++; temp[temp.length - 1].count = last.count }``` 我认为如果不这样做，```last.count++``` 就不能反映在 ```temp``` 数组中。由于我不熟悉 JS，所以我尝试在 Swift 上实现它。 - Zhou Haibo

为什么？“last”包含了指向最后一个对象的引用，如果存在的话。 - Nina Scholz

Answer 2

这是一个可能的解决方案，时间复杂度为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]));
```

该解决方案在输入列表的每个位置计算“分数”，计算不超过2个不同值的序列的长度，然后获取得分最高的结果并根据该信息从原始列表中提取一个片段。它肯定可以进行清理和优化，但我认为这是一个很好的起点。

- alebianco

---

该解决方案的最坏运行时间复杂度为O(n²)，而不是O(n)。考虑输入[1,1,1,...,1]，其中有n个相同的元素。现在，内部for循环永远不会中断，因此执行O(n)次计算，加上外部reduce循环，最终成为O(n²)。 - le_m

Answer 3

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

这个解决方案检查了数组的每一个可能的子串，检查它是否有不超过2个不同的数字，并最终打印出最长子串的长度。

- opp

---

这很完美。你能解释一下你的思考过程吗？我一开始理解问题时有些困难。 - Filth

目标是找到包含不超过两个不同数字的最长数字序列。 该代码生成每个可能的数组切片（使用for循环）并生成该数组的唯一数字集合 （Set是ES6本机对象，用于存储唯一值，“...”操作符将集合转换回数组）。 如果该唯一数组的长度小于3，则该数组是有效的解决方案候选者。 最后，它检查当前数组切片的长度是否大于迄今为止遇到的最大长度，如果是，则将其存储在max中。 - opp

这个解决方案需要进行 n*(n+1)*(n+2)/6 次操作来计算最大值，对应于运行时复杂度为 O(n³)。与可用的线性解决方案相比，这是非常糟糕的。 - le_m

Answer 4

使用滑动窗口算法在O(n)时间内：

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

- arnavpanwar99