주어진 목록에서 '최상'요소 찾기

비교가를 이행 적되지 "이 요소의 목록입니다. 그리고 당신은 찾을 수있다"목록에서 가장 "요소. 요소는 서로 비교할 수 있지만, . 예 경우 > B 및 B> C이면 A는 C보다 클 필요가 없습니다.

최상의 요소를 대답으로 반환해야합니다. 이는 목록의 다른 모든 요소보다 우수합니다. 그러한 요소가 없으면 null을 반환합니다. "

내 용액 :

시도 1

간단한 O (N^2) 용액. 각 요소를 서로 다른 요소와 비교합니다.

면접자가 만족하지 못했습니다.

시도 2 :

시작 이후 두번째 요소와 함께 첫 번째 요소를 비교. 'E'요소 중 A> E 일 경우 E를 표시하고 (다른 배열/목록 등을 사용할 수 있음) 더 이상의 비교를 위해 E를 고려하지 않습니다. 이것은 E보다 더 좋은 적어도 하나의 요소가 있기 때문에 E가 분명히 답이 아니기 때문입니다.

복잡도는 여전히 이전 시도와 비교하여 약간 개선 된 O (n^2)이고, 여전히 이다.

그는 여전히 만족하지 않았습니다. 누구든지 더 나은 해결책을 찾아 낼 수 있습니까?

출처

2012-01-02 Bhushan

나는 최대 힙이 해결책일지도 모른다고 생각했지만, 비교가 이항 적이 아니기 때문에, 좋지 않을 것이다. ?? – brainydexter

@brainydexter : 예, 비교가 추이 적이 지 않으므로 힙과 같은 데이터 구조는 작동하지 않습니다. – Bhushan

확실히. 너는 N 개의 원소를 가지고있다. 처음 두 개를 비교하십시오. 이들 중 하나는 다른 것보다 '악화'입니다. 그것을 버리십시오. 두 요소의 '더 나은'요소를 다음 요소와 비교하십시오. 하나의 요소 만 남을 때까지 목록에서 첫 번째 단계를 계속합니다. 이 단계는 O (N)입니다.

첫 번째 단계에서 살아남은 요소 중 하나가 이미 비교 된 요소를 제외하고는 원래 요소의 모든 요소와 비교되어야합니다. 일단 '잃어 버리면'최고의 요소가 없다고 회신합니다. 이 단계에서 모든 비교가 '이기면'이 요소를 반환합니다. 이 단계는 또한 O (N)입니다.

이 알고리즘은 최악의 경우 O (N + N) = O (N)이고 최상의 경우 O (N + 0) == O (N)입니다. 또한 솔루션을 확인하는 것이 O (N)이기 때문에 이것이 가능한 최고의 복잡성임을 입증 할 수 있으며 솔루션을 확인하는 것보다 솔루션을 얻는 것이 덜 복잡 할 수 없습니다.

출처

2012-01-02 20:05:23 Dan

이것은 설득력있게 들립니다. 그러나 첫 번째 패스의 결과가 적어도 하나의 다른 요소보다 큰 요소일까요? 즉 반환 된 요소에 대해 고유 한 것이 없습니다. –

그러나 올바른 요소는 하나의 다른 요소보다 * 더 * * 더 * 확실하지 않은 유일한 요소입니다. 하나를 제외하고는 다른 모든 요소보다 나쁠 수 있으므로 두 번째 패스가 필요한 이유입니다.첫 번째 단계는 하나의 후보로 좁힐 수있는 간단한 방법입니다. – Dan

@ Dan : 당신은 고용되었습니다 !!! – Bhushan

주어진 목록에서 '최상'요소 찾기

답변

관련 문제