84669인 학습
152542인 학습
20005인 학습
5487인 학습
7821인 학습
359900인 학습
3350인 학습
180660인 학습
48569인 학습
18603인 학습
40936인 학습
1549인 학습
1183인 학습
32909인 학습
var arr = [1,2,3,9,9,9,9,6,7,8,10,10,10,15]
找出连续重复元素的起始索引,求一个复杂度较低的算法?
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 ] ] }
跟 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):
运行结果:
![](http://img.php.cn/upload/image/000/000/000/6a7c9bae2a4496861e58c65c9fed66ee-0.png)
Update
看了其他人的答案里给出了起始和终止的位置,我也来凑个热闹。
运行结果:
![](http://img.php.cn/upload/image/000/000/000/615cc25ed8004153baf749cd03c78c70-1.png)