배열의 첫 번째 줄과 나머지 줄의 가장 낮은 차이를 찾아야합니다.

Question

글쎄, 나는 (s,h)의 수의 쌍을 받았습니다. 여기서 s은 요소를 2 차원 배열의 s 요소로 보냅니다. 각 행마다 동일한 양의 요소가있을 필요는 없으며 행에 N 개 이상의 요소가있을 수 없다는 것을 알고 있습니다.

내가 원하는 것은 첫 번째 줄의 특정 요소와 나머지 요소 사이에 가장 큰 차이 (!)를 찾는 것입니다.

(101,92) (100,25,95,52,101) (93,108,0,65,200)과 3 줄이 있으면 3을 선택해야합니다. 왜냐하면 92를 선택해야하기 때문에 95-92 = 3을 1에서 2로, 93-92 = 1에서 3을 1로 설정합니다.

나는 내가 다음 n(i) 요소 각각 i=0..s, n0<=n1<=...<=ns와 s 라인이있는 경우 다른 방향으로 1 라인에서 최적 따기 때 좋은 평균 성능 시나리오가 너무 같은 것이 확실 지점에 도달했습니다.

그러나, 나는 O보다 낮은 방법을 생각할 수 없습니다 (N ²) 또는 어쩌면 O (N ³) 경우도있다. 누구든지이 일을 상당히 개선 된 방법에 대한 제안을 가지고 있습니까?

Answer 1

모든 행을 단일 목록으로 결합하고 어디에서 오는 요소를 추적합니다.

이 목록을 정렬하십시오.

각 행에 대해 마지막 값 변수가 있습니다.

정렬 목록의 각 항목에 대해 적용 가능한 목록의 마지막 값 변수를 업데이트하십시오. 모든 행에 마지막 값 세트가 아직없는 경우에는 아무 것도하지 마십시오. 그 첫 번째 목록에서 요소가 있다면 :

• 마지막 값 변수의 모든의 가장 큰 차이를 다시 계산. 이 차이점을 저장하십시오.

는 다른 목록에서 요소의 경우 모든 값이 이전에 설정되지 않은 경우

• 는 큰 차이를 계산합니다. 그렇지 않으면 첫 번째 목록의 마지막 값과이 요소의 차이가 가장 큰 차이보다 큰 경우 가장 큰 차이점을이 차이로 업데이트하십시오. 이 차이점을 저장하십시오.

가장 작은 차이가 원하는 값입니다.

예 : 필요

Lists: (101,92) (100,25,95,52,101) (93,108,0,65,200) 

Sorted 0 25 52 65 92 93 95 100 101 101 108 200 
Source 2 1 1 2 0 2 1 1 0 1 2 2 

Last[0] - - - - 92 92 92 92 101 101 101 101 
Last[1] - 25 52 52 52 52 95 100 100 101 101 101 
Last[2] 0 0 0 65 65 93 93 93 93 93 108 200 

Diff - - - - 40 41 3 8 8 8 7 9 
Best - - - - 40 40 3 3 3 3 3 3 

= 3 베스트. 실제 항목을 저장하거나 나중에 찾으면됩니다.

복잡성 :

n이 전체 항목 수와 k이 목록의 숫자하자.

O(n log n) 결합 + 정렬.

O(nk) (최악의 경우), 우리가 n 항목을 확인하고 있으며, 각 항목에서 최대로 O(k)의 작업을 수행합니다.

so O(n log n + nk).