JavaScript의 효율적인 알고리즘은 무엇입니까?-JS 튜토리얼-php.cn

JavaScript의 효율적인 알고리즘은 무엇입니까?

亚连

풀어 주다： 2018-06-11 15:07:45

원래의

1824명이 탐색했습니다.

이 글에서는 JavaScript를 사용하여 배열의 중복 요소를 삭제하기 위해 일반적으로 사용되는 5가지 효율적인 알고리즘을 주로 소개합니다. JavaScript의 배열에서 중복 요소를 삭제하는 몇 가지 일반적인 작동 기술을 예제 형식으로 요약하고 분석합니다.

이 문서의 예에서는 JavaScript가 배열에서 중복 요소를 제거하기 위해 일반적으로 사용되는 5가지 효율적인 알고리즘을 구현하는 방법을 설명합니다. 참고할 수 있도록 모든 사람과 공유하세요. 자세한 내용은 다음과 같습니다.

JS에서 배열 중복 제거를 구현하는 방법에 대한 5가지 방법이 있으며 데모와 소스 코드가 첨부되어 있습니다.

1. 배열 순회 방법

중복을 제거하는 가장 간단한 방법,

구현 아이디어: 새 배열을 만들고, 들어오는 배열을 순회하고, 값이 없으면 새 배열에 추가합니다. 새 배열에 주의하세요. 값이 배열에 있는지 확인하는 메서드는 ECMAScript5 메서드입니다. IE8 이하 버전에서는 소스 코드를 더 작성해야 합니다.

// 最简单数组去重法
function unique1(array){
 var n = []; //一个新的临时数组
 //遍历当前数组
 for(var i = 0; i < array.length; i++){
  //如果当前数组的第i已经保存进了临时数组，那么跳过，
  //否则把当前项push到临时数组里面
  if (n.indexOf(array[i]) == -1) n.push(array[i]);
 }
 return n;
}
// 判断浏览器是否支持indexOf ，indexOf 为ecmaScript5新方法 IE8以下（包括IE8， IE8只支持部分ecma5）不支持
if (!Array.prototype.indexOf){
 // 新增indexOf方法
 Array.prototype.indexOf = function(item){
  var result = -1, a_item = null;
  if (this.length == 0){
   return result;
  }
  for(var i = 0, len = this.length; i < len; i++){
   a_item = this[i];
   if (a_item === item){
    result = i;
    break;
   } 
  }
  return result;
 }
}

로그인 후 복사

2. 개체 키-값 페어링 방법

이 방법은 다른 방법보다 실행 속도가 빠르지만 메모리를 더 많이 차지합니다.

구현 아이디어: 새로운 js 개체를 만들고 새 배열을 만들고, 들어오는 배열을 순회할 때 값이 js 객체의 키인지 확인하고, 그렇지 않은 경우 키를 객체에 추가하고 새 배열에 넣습니다. 참고: js 객체 키인지 확인할 때 "toString()"은 수신 키에서 자동으로 실행됩니다. 예를 들어 a[1], a["1"]과 같이 다른 키가 동일한 것으로 오해될 수 있습니다. 위의 문제를 해결하려면 여전히 "indexOf"를 호출해야 합니다.

// 速度最快， 占空间最多（空间换时间）
function unique2(array){
 var n = {}, r = [], len = array.length, val, type;
  for (var i = 0; i < array.length; i++) {
    val = array[i];
    type = typeof val;
    if (!n[val]) {
      n[val] = [type];
      r.push(val);
    } else if (n[val].indexOf(type) < 0) {
      n[val].push(type);
      r.push(val);
    }
  }
  return r;
}

로그인 후 복사

3. 배열 첨자 판단 방법

여전히 "indexOf"를 호출해야 하지만 성능은 방법 1과 유사합니다.

구현 아이디어: 현재 배열의 i번째 항목이 나타나는 경우 현재 배열의 첫 번째 위치가 i가 아닌 경우 i번째 항목이 반복되고 무시된다는 의미입니다. 그렇지 않으면 결과 배열을 저장합니다.

function unique3(array){
 var n = [array[0]]; //结果数组
 //从第二项开始遍历
 for(var i = 1; i < array.length; i++) {
  //如果当前数组的第i项在当前数组中第一次出现的位置不是i，
  //那么表示第i项是重复的，忽略掉。否则存入结果数组
  if (array.indexOf(array[i]) == i) n.push(array[i]);
 }
 return n;
}

로그인 후 복사

4. 정렬 후 인접 제거 방법

네이티브 배열의 "정렬" 방법의 정렬 결과는 그다지 신뢰할 수 없지만, 이러한 단점은 순서에 주의를 기울이지 않는 중복 제거에는 영향을 미치지 않습니다.

구현 아이디어: 들어오는 배열을 정렬합니다. 정렬 후에는 동일한 값이 인접해 있으며, 순회할 때 이전 값과 중복되지 않는 값만 새 배열에 추가합니다.

// 将相同的值相邻，然后遍历去除重复值
function unique4(array){
 array.sort(); 
 var re=[array[0]];
 for(var i = 1; i < array.length; i++){
  if( array[i] !== re[re.length-1])
  {
   re.push(array[i]);
  }
 }
 return re;
}

로그인 후 복사

5. 최적화된 배열 탐색 방법

이 방법의 구현 코드는 매우 훌륭합니다.

구현 아이디어: 중복 없이 가장 적합한 값을 가져와서 새 항목에 넣습니다. 정렬. (중복된 값이 감지되면 현재 루프가 종료되고 최상위 루프의 다음 라운드 판단이 시작됩니다.)

// 思路：获取没重复的最右一值放入新数组
function unique5(array){
 var r = [];
 for(var i = 0, l = array.length; i < l; i++) {
  for(var j = i + 1; j < l; j++)
   if (array[i] === array[j]) j = ++i;
  r.push(array[i]);
 }
 return r;
}

로그인 후 복사

위 내용은 모두를 위해 정리한 내용입니다. 미래.