var arr = [1,2,3,9,9,9,9,6,7,8,10,10,10,15]
找出连续重复元素的起始索引,求一个复杂度较低的算法?
雷雷
@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);
运行结果:
看了其他人的答案里给出了起始和终止的位置,我也来凑个热闹。
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);
雷雷
@boxsnake
雷雷 雷雷跟 boxsnake 一样是 O(n):
运行结果:
Update
看了其他人的答案里给出了起始和终止的位置,我也来凑个热闹。
运行结果: