선형 시간에서 두 번째로 큰 요소를 찾기 위해 배열 탐색

Question

배열의 두 번째로 큰 요소를 찾을 수있는 선형 시간의 길이 있습니까? 배열 요소는 양수, 음수 또는 0 일 수 있습니다. 요소가 반복적 일 수 있습니다. 허용되는 STL이 없습니다. Python을 사용할 수 있습니다.

해결책 : 배열을 정렬하고, 두 번째 요소를 가지고 있지만 는

변경을 허용하지 소트 : 정의 요소에 의해 두 번째로 큰 수치의 작은 한 것이다. 마찬가지로 우리가있는 경우

ARR = {5,5,4,3,1} 그런 다음 두 번째로 큰 내가 덜 최대 규모의 복잡성을 KTH하는 질문을 일반화하려는 경우 말할 수 4

추가 입니다 nlogn과 같이 선형 적이기 때문에 해결책이 될 수 있습니다. 사이즈 3의 임시 배열을 생성

Answer 1

진정한 O (n) 알고리즘을 원한다면 array에서 n 번째로 큰 요소를 찾고 싶다면 quickselect (근본적으로 당신이 관심이없는 파티션을 던지는 quicksort)과 아래 좋은 작성자는 런타임 분석이다 :

http://pine.cs.yale.edu/pinewiki/QuickSelect

Answer 2

• ,
• 가 제 3 개 요소를 복사
• 일종의 임시 배열
• 소스 배열에서 4 번째 원소로 임시 배열의 마지막 교체 ,
• 종류의 임시 배열,
• 는
• 종류의 임시을 소스 배열에서 5 요소와 임시 배열의 마지막을 대체 어레이
등

크기 (3)의 배열은 일정한 시간 및 소스 어레이의 각 요소에 따라서 선형 전체 시간 동안 한번 수행 정리.

Answer 3

당신이 할 수있는,이 의사 알고리즘 :

max = 2max = SMALLEST_INT_VALUE; 

for element in v: 
    if element > max: 
     2max = max; 
     max = element; 

    else if element > 2max: 
     2max = element; 

2max 당신이 찾고있는 값입니다.

알고리즘은 요소가 동일한 배열과 같은 특정 경우에 대해 올바른 값을 반환하지 않습니다.

Answer 4

2 개의 메모리 슬롯을 유지하면서 배열을 살펴보고 지금까지 본 2 개의 가장 큰 요소를 기록합니다. 두 개 중 작은 것을 반환하십시오.

.... 내가 볼 수없는이 질문에 대해 까다로운 것이 있습니까?

Answer 5

의사 코드 :

int max[2] = { array[0], array[1] } 

if(max[1] < max[0]) swap them 

for (int i = 2; i < array.length(); i++) { 
    if(array[i] >= max[0]) max[1] = max[0]; max[0] = array[i] 
    else if(array[i] >= max[1]) max[1] = array[i]; 
} 

지금, 최대 어레이는 최대 2 개 요소를 포함한다.

Answer 6

네. 이 태그를 C/C++로 태그했지만 파이썬에서 할 수 있다고 언급했습니다. 어쨌든 알고리즘은 다음과 같습니다.

1. 배열을 만듭니다 (분명히).
2. 첫 번째 항목이 두 번째 항목보다 큰 경우 첫 번째 변수를 첫 번째 항목으로 설정하고 두 번째 변수를 두 번째 항목으로 설정하십시오. 그렇지 않으면, 그 반대도 마찬가지입니다.
3. 모든 항목을 반복합니다 (처음 두 항목 제외).
4. 배열의 항목이 첫 번째 변수보다 큰 경우 두 번째 변수를 첫 번째 변수로 설정하고 첫 번째 변수를 항목으로 설정합니다. 그렇지 않으면 항목이 두 번째 변수보다 큰 경우 두 번째 변수를 항목에 설정합니다.

두 번째 변수는 사용자의 대답입니다.

list = [-1,6,9,2,0,2,8,10,8,-10] 

if list[0] > list[1]: 
     first = list[0] 
     second = list[1] 
else: 
     first = list[1] 
     second = list[0] 

for i in range(2, len(list)): 
     if list[i] > first: 
       first, second = list[i], first 
     elif list[i] > second: 
       second = list[i] 

print("First:", first) 
print("Second:", second) 

Answer 7

// assuming that v is the array and length is its length 
int m1 = max(v[0], v[1]), m2 = min(v[0], v[1]); 

for (int i=2; i<length; i++) { 
    if (likely(m2 >= v[i])) 
    continue; 
    if (unlikely(m1 < v[i])) 
    m2 = m1, m1 = v[i]; 
    else 
    m2 = v[i]; 
} 

당신이 필요로하는 결과는 (당신이 그들을 필요로하지 않는 경우에, 당신은 간단하게 제거 할 수 있습니다 가능성과 가능성 매크로 성능을 위해 here로 정의) m2입니다.

Answer 8

다른 답변은 [0, 1, 1]과 같은 배열에서 두 번째로 큰 0 (업데이트 된 문제 정의에 따라)이라는 사실을 설명하지 못했다고 생각합니다. 게다가, quickselect의 모든 언급은 O (n)이 아니라 오히려 O (n^2)이며 필요한 것보다 훨씬 많은 작업을 수행하고 있습니다 (그 위에는 문제 문이 허용하지 않는 정렬 알고리즘이 있습니다). Simone과 매우 유사한 알고리즘이 있지만 두 번째로 큰 고유 요소를 반환하도록 업데이트되었습니다.

def find_second(numbers): 
    top = numbers[0] 
    second = None 

    for num in numbers[1:]: 
     if second is None: 
      if num < top: second = num 
      elif num > top: 
       second = top 
       top = num 
     else: 
      if num > second: 
       if num > top: 
        second = top 
        top = num 
       elif num < top: second = num 

    if second is not None: return second 
    return top 

if __name__ == '__main__': 
    print "The second largest is %d" % find_second([1,2,3,4,4,5,5])