javascript - 找出数组中连续重复元素的起始索引?
学习ing
学习ing 2017-06-26 10:51:51
0
3
1206
var arr = [1,2,3,9,9,9,9,6,7,8,10,10,10,15]

找出连续重复元素的起始索引,求一个复杂度较低的算法?

学习ing
学习ing

全部回复(3)
Peter_Zhu

雷雷


@boxsnake

雷雷 雷雷
学霸

跟 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))
代言
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);

运行结果:

热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板