재귀를 사용하여 배열에서 두 번째로 큰 원소 찾기

Question

제목에서 말했듯이 재귀를 사용하여 배열에서 두 번째로 큰 원소를 찾는 효율적인 방법이 있습니까?

Answer 1

partition based Selection algorithm 자연에 의해 재귀 적이며, 그래서를 사용하면, 배열의 요소 번째 '는 k를 선택할 수 있습니다 - 당신은 실제로 k = n-1 (귀하의 경우)를 포함한 모든 k에 대한 답을 찾을 수 있습니다.

이것은 평균적으로 상당히 낮은 상수로 O(n)에서 수행됩니다. 이런 O(n)에

Answer 2

배열에 대해 알려진 것이 없으면 재귀 적이거나 반복적이든간에 O(n) 이상을 수행 할 수 없습니다.

두 개의 가장 큰 요소를 전달하고 더 큰 값을 찾으면 대체하면서 재귀 적으로 통과합니다.

find_largest(array_begin, largest, secondLargest) 
    if (array_begin = NULL) 
     return secondLargest 
    if (array_begin.value > largest) 
     secondLargest = largest 
     largest = array_begin.value 
    return find_largest(array_begin+1, largest, secondLargest) 

largest 및 secondLargest는 처음에 당신이 배열에서 찾을 것으로 예상되는 최소로 설정 될 수있다.

당신이 옳아 요, 정렬 (적어도 전체 정렬)은 잔인합니다.

Answer 3

예시 :

int findSecondLargest(int[] arr, int index, int largest, int secondLargest) { 
    if(index == arr.length) { 
     return secondLargest; 
    } 
    int element = arr[index]; 
    if(element > secondLargest) { 
     if(element > largest) { 
      return findSecondLargest(arr, index + 1, element, largest); 
     } else { 
      return findSecondLargest(arr, index + 1, largest, element); 
     } 
    } 
    return findSecondLargest(arr, index + 1, largest, secondLargest); 
} 

Answer 4

public void recurs(int[] data, int ind, int max1, int max2){ 
     if(ind<data.length){ 
      if(data[ind]>max1){ 
       int temp = max1; 
       max1 = data[ind]; 
       max2 = temp; 
      } else if(data[ind]>max2){ 
       max2 = data[ind]; 
      } 
      recurs(data, ind+1, max1, max2); 
     } else { 
      return max2; 
     } 
     return -1; 
    } 

그것을 호출 : 은 (DATAX, 0는 Integer.MIN_VALUE,는 Integer.MIN_VALUE)를 되풀이;

Answer 5

본능적으로 배열을 스캔하고 모든 값을 두 번 비교할 수 있습니다. 어쨌든 문제를 해결하려면 O (n)가 필요합니다. 충분히 빠릅니다.

무료가 아니기 때문에 필요하지 않은 경우 재귀 적으로 발생하지 않도록하십시오.

Answer 6

재귀로 수행하는 경우 최대 3 (n)/2-2 비교를 수행해야하지만 더 나은 솔루션을 얻으려면 n 개의 노드가있는 이진 트리로 생각하십시오. 그런 다음 두 번째로 큰 log (n) -1 비교를 찾는 n-1 비교가 있습니다. 그러나 일부에서는 n + log (n) 비교가 필요하다고 주장합니다.