javascript - 找出陣列中連續重複元素的起始索引？

Question

var arr = [1,2,3,9,9,9,9,6,7,8,10,10,10,15]

找出連續重複元素的起始索引，求一個複雜度較低的演算法？

Answer 1

雷雷

---

@boxsnake

雷雷 雷雷

Answer 2

跟 boxsnake 一樣是 O(n)：

var result = {}
for (let i = 1; i < arr.length; i += 1) {
  if (arr[i] === arr[i - 1]) {
    if (result[arr[i]]) {
      result[arr[i]].push(i - 1)
    } else {
      result[arr[i]] = [i - 1]
    }
    while (i < arr.length && arr[i] === arr[i + 1]) {
      i += 1
    }
  }
}
console.log(JSON.stringify(result))

Answer 3

var result = [],
    flag = true;
    // 此处flag为true表示可以切换此标识，反之就不可切换
    // 当相邻的两个元素相等时，如果标识可切换就说明是刚开始重复
    // 如果标识不可切换，就说明是在某一段连续重复中还没结束
    // 如果相邻的不相等，且标识可切换，就说明此处不连续重复
    // 如果标识可切换，就说明此处是连续重复的中断处
    // 这样，就可以切换标签，然后供下一次连续开始是把标记再切换回来

for(var i = 0, len = arr.length; i < len - 1; i++) {
    if(arr[i] == arr[i + 1] && flag) { // 可以切换标识且连续相等->重复开始
        result.push(i);
        flag = false;
    } else if(arr[i] != arr[i + 1] && !flag) { // 不可以切换标识但两者不等->重复结束
        flag = true;
    }

    // 剩余两种情况不做任何操作
    // 总体来说，就是flag = true就在重复之外，否则就在重复之内
    // 在重复之外时，如果前后两个相等就切换标记，重复开始
    // 在重复之内时，如果前后两个不等就切换标记，重复结束
}

console.log(result);

運行結果：

Update

看了其他人的答案裡給了起始和終止的位置，我也來湊個熱鬧。

var result = [],
    current = [], // 起始和终止位置缓存
    flag = true;

for(var i = 0, len = arr.length; i < len - 1; i++) {
    if(arr[i] == arr[i + 1] && flag) {
        current[0] = i; // 记录起始位置
        flag = false;
    } else if(arr[i] != arr[i + 1] && !flag) {
        current[1] = i; // 记录终止位置
        result.push(current);
        current = []; // 重置缓存
        flag = true;
    }

    // 下面这段代码是为了判断是否在循环中且数组遍历到最后，如果是，在循环中需要跳出记录，但是可以不用重置缓存和切换标识，直接跳出，主体部分和上面记录终止位置类似
    if(i == len - 2 && arr[i] == arr[i + 1] && !flag) { // 注意此处是len - 2
        current[1] = i + 1; // 注意是i + 1
        result.push(current);
        break;
    }
}

console.log(result);

運行結果：