복잡 한 데이터 형식 을 포함 한 배열 의 무 거 운 문 제 를 이야기 하 다.
7014 단어 알고리즘
_.isEqual
배열 의 무 게 를 실현 하려 면, 우 리 는 먼저 두 데이터 가 같은 지 비교 하 는 함수 가 있어 야 한다.Underscore. js 는 우리 에 게 좋 은 기능 함 수 를 제공 합 니 다. 이름 은:...isEqual()。복합 데이터 형식 에 대한 비교 에 있어 서 스 택 (후진 후 출) 과 유사 한 두 개의 배열 (push () 과 pop () 방법 만 호출 하여 스 택 을 실현 합 니 다) 을 도입 하고 재 귀적 인 방식 으로 끼 워 넣 어 판단 합 니 다.그 소스 코드 는 다음 과 같다.
// eq isEqual ,
// === , eq
// , , ( )
var eq = function(a, b, aStack, bStack) {
//
// , ,
// 0, -0, 0 === -0
// 1 / 0 == 1 / -0 (1 / 0 Infinity, 1 / -0 -Infinity, Infinity -Infinity)
if (a === b) return a !== 0 || 1 / a == 1 / b;
// false, ( null undefined )
if (a == null || b == null) return a === b;
// Underscore ( _ )
// ( _wrapped ),
// jQuery DOM , DOM
// , Object.prototype.toString() , false,
if (a instanceof _) a = a._wrapped;
if (b instanceof _) b = b._wrapped;
var className = toString.call(a);
// , false
if (className != toString.call(b)) return false;
switch (className) {
// , ,
case '[object String]':
// toString() , :
// Object.prototype.toString.call(new String('5'))-->"[object String]"
// Object.prototype.toString.call('5')-->"[object String]"
return a == String(b);
case '[object Number]':
// +a a Number, a , a NaN
// NaN NaN , a NaN , a == b , b NaN( b != +b)
// a NaN , a 0, b -0 , 0 === -0 ( )
return a != +a ? b != +b : (a == 0 ? 1 / a == 1 / b : a == +b);
// return break, ( Boolean , Boolean )
case '[object Date]':
case '[object Boolean]':
// Coerce dates and booleans to numeric primitive values. Dates are compared by their
// millisecond representations. Note that invalid dates with millisecond representations
// of `NaN` are not equivalent.
//
// ( NaN, )
// , true 1, false 0
//
return +a == +b;
// RegExps are compared by their source patterns and flags.
// , source
//
// ( g, i, m)
// ,
case '[object RegExp]':
return a.source == b.source &&
a.global == b.global &&
a.multiline == b.multiline &&
a.ignoreCase == b.ignoreCase;
break;
// , Underscore true:
// _.isEqual({a:1},{a:1});// true
// false:
// _.isEqual({a:function(){}},{a:function(){}}); // false
// ( ), , true
case '[object Function]':
var repReg = /\r|
|\t|\v|\s*/g;
return a.toString().replace(repReg,'') === b.toString().replace(repReg,'');
}
// , ab
if (typeof a != 'object' || typeof b != 'object') return false;
// 。 ES 15.12.3 ( ), 'JO'
var length = aStack.length;
while (length--) {
// 。 。
// 。
if (aStack[length] == a) return bStack[length] == b;
}
// , Object instanceof Object true,Function instanceof Function true,
var aCtor = a.constructor, bCtor = b.constructor;
if (aCtor !== bCtor && !(_.isFunction(aCtor) && (aCtor instanceof aCtor) &&
_.isFunction(bCtor) && (bCtor instanceof bCtor))) {
return false;
}
// Add the first object to the stack of traversed objects.
//
aStack.push(a);
bStack.push(b);
var size = 0, result = true;
// Recursively compare objects and arrays.
//
if (className == '[object Array]') {
// Compare array lengths to determine if a deep comparison is necessary.
// size , false
size = a.length;
result = size == b.length;
if (result) {
// Deep compare the contents, ignoring non-numeric properties.
// , ( )
while (size--) {
if (!(result = eq(a[size], b[size], aStack, bStack))) break;
}
}
} else {
// Deep compare objects.
//
for (var key in a) {
if (_.has(a, key)) {
// Count the expected number of properties.
//
size++;
// Deep compare each member.
//
if (!(result = _.has(b, key) && eq(a[key], b[key], aStack, bStack))) break;
}
}
// Ensure that both objects contain the same number of properties.
// true, b a b a , true。 ( )
if (result) {
for (key in b) {
if (_.has(b, key) && !(size--)) break;
}
result = !size;
}
}
// Remove the first object from the stack of traversed objects.
// “ ” push , 。
aStack.pop();
bStack.pop();
return result;
};
// Perform a deep comparison to check if two objects are equal.
_.isEqual = function(a, b) {
return eq(a, b, [], []);
};
특히 주의해 야 할 것 은 Underscore 대.isEqual({a:1},{a:1});의 결 과 는 true 이 고, 대.isEqual({a:function(){}},{a:function(){}});의 결과 가 false 라 는 점 은 나 로 하여 금 특히 이해 하지 못 하 게 한다.나 는 그 소스 코드 를 작은 변경 하여 후자 의 비교 도 true 로 만 들 었 다.
배열 제거
위 에서 두 개의 임 의 값 이 기다 리 고 싶 은 지 비교 하 는 함수 가 있 으 면 우 리 는 배열 의 무 거 운 조작 을 할 수 있다.
우 리 는 가장 간단 한 이중 순환 방식 으로 실현 합 니 다. 코드 는 다음 과 같 습 니 다.
function removeRepeat(ary){
var len = ary.length;
for(var i=0;i
최 악의 경우 알고리즘 의 시간 복잡 도 계산 공식 은 n * (n - 1) + (n - 1) * (n - 2) +... 2 * 1 이 고 결 과 는 O (n ^ 2) 이다.
또 하나의 실현 은 빈 배열 을 정의 한 다음 왼쪽 에서 오른쪽으로 무 거 운 배열 을 옮 겨 다 니 며 값 push 를 빈 배열 로 옮 겨 다 니 며 다음 값 으로 옮 겨 다 닐 때 이 값 이 배열 의 값 과 중복 되 는 지 여 부 를 판단 하고 중복 이 있 으 면 조작 하지 않 으 며 중복 이 없 으 면 push 를 배열 에 넣 는 것 입 니 다.이러한 시간 복잡 도 는 1 + 2 + 3 +... + (n - 1) 이 고 결 과 는 O (n * (n - 1) / 2) 이 며 O (n ^ 2) 이다.
비교적 효율 적 인 알고리즘 이 실현 되 었 는 지 모르겠다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.