javascript - Finden Sie den Startindex aufeinanderfolgender sich wiederholender Elemente in einem Array?

Question

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

Finden Sie den Startindex aufeinanderfolgender wiederholter Elemente. Suchen Sie nach einem Algorithmus mit geringerer Komplexität?

Answer 1

var arr = [1,2,3,9,9,9,9,6,7,8,10,10,10,15]
var dic = {}
for (k in arr){
     if (!dic[arr[k]]){dic[arr[k]] = [k]}
     else{dic[arr[k]][1] = k}
 }
for (k in dic){if (dic[k].length==1){delete(dic[k])}}

console.log(dic)
{ '9': [ '3', '6' ], '10': [ '10', '12' ] }

---

@boxsnake

var arr = [1,2,3,9,9,9,9,6,7,9,9,9,8,10,10,10,15,10,10]
var dic = {}
for (k in arr){
    k = Number(k)
    if(arr[k]==arr[k-1]||arr[k]==arr[k+1]){
        if (!dic[arr[k]]){dic[arr[k]] = [[k,k]];continue}
        s = dic[arr[k]].slice(-1)[0]
        if(k-s[1]==1){s[1]=k}
        else{dic[arr[k]].push([k,k])}
    }
}
console.log(dic)

{ '9': [ [ 3, 6 ], [ 9, 11 ] ],
  '10': [ [ 13, 15 ], [ 17, 18 ] ] }

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

运行结果：