문제

순열의 실행을 단일 숫자로 매핑 할 수있는 알고리즘이 필요하지만 후속 숫자도 줄일 수 있습니다.

따라서 실행은 순열의 순차적 숫자 세트입니다. 목록에서, 1; 2; 3; 5; 6; 4 두 개의 런, 1; 2; 3 및 5; 6. 이것들을 단일 숫자, 최소로 바꾸고 싶습니다. 따라서 실행을 제거한 후 4 가지 요소의 순열이 있으면 순열이 숫자 1 ... 4를 사용합니다. 위의 두 실행을 줄여야합니다. . 첫 번째 실행은 1, 4가 2로 변환되고 [5; 6]은 3으로 변환되며, 두 번째 기준을 유지합니다. 감소 된 순열을 정렬하면 매핑에서 내부의 요소를 확장하고 원래 순열을 정렬하면 동일한 결과를 얻을 수 있습니다. 결과적 순열에는 실행이 없어야합니다.

예를 들어 (실행을 강조했습니다) :

(1;2;3;4;5;6) => 1 //Mappings: 1->1;2;3;4;5;6
(2;3;4);1;(5;6) => 2 1 3 // Mappings: 2->2;3;4, and 3->5;6
(3;4);(1;2);(5;6) => 2 1 3 // Mappings: 2->3;4, and 1->1;2 and 3->5;6

지금은 목록을 넘어서 목록 목록을 만들고 달리기를 그룹화하고 있습니다. 실제로 두 번째 부분은 깨끗한 솔루션을 만드는 데 어려운 부분입니다. 나는 순진한 접근법을 생각했습니다. 누군가가 내 것보다 더 잘 할 수있는 영리한 트릭을 가지고 있다면, 나는 O (2n + n log n)와 같습니다.

  • 실행을 실행의 헤드 요소로 교체하고 해당 데이터를 해시 가능에 삽입합니다 (복구 가능성)
  • 정렬 된 인덱스라면 누락 된 숫자에 대한 맵을 만들기 위해 정렬. [1; 6; 5; 4]는 [(1,1); (4,2); (5,3); (6,4)를 출력 할 것입니다.
  • STEP1의 목록을 STEP2에서 작성한 맵으로 대체하고 번역을위한 해시 테이블을 업데이트합니다.

다시 예제를 통해 실행 :

step 1: replace runs with the head element of the run and inserting data into a hash table  
    [1;3;4;2;5;6;] -> [1;3;2;5]  
step 2: sort array to create map  
    [1235], so we know that, in the previous array, 1 maps to 1, 2 to 2, 3 to 3, 4 to 5.  
step 3: do above translation on array from step one. 
    [1;3;2;4]

내가이 순열을 분류하고 재구성한다면 : [1; 2; 3; 4], 3-> 3; 4 및 4-> 5; 6 I를 얻는다, 1; 2; 3; 4; 5; 6. 또한 정렬되었습니다.

목록을 사용하고 있으므로 기능적 접근 방식이 선호됩니다. 코드가 필요하지 않습니다. 물론 모든 아이디어는 환영합니다.

편집하다:

mweerden :

매핑의 정확한 조건이 무엇인지는 확실하지 않습니다. 왜 정확히 n 런의 순열에 대한 순열 [1,2, ..., n]을 생성하는 것이 허용되지 않습니까? 당신은 그 실행에서 숫자에 달리기를 맵핑하는 것을 선호하는 것 같지만 (이것은 항상 가능하지는 않기 때문에) 자유를 허용하는 것 같습니다. -

나는 그 실행 내의 숫자에 달리기를 맵핑하는 것을 선호하지 않지만 (위의 봐!), 나는 보존해야한다. 주문. 순열 [1; 2; 3 ... n ~이다 달리기, 따라서 더 줄일 수 있습니다. 그렇기 때문에 유효하지 않습니다. 순서는 다른 알고리즘의 추가 작업에서 중요하지만, 개별 요소는 끝에서 확장되어 원래 순열을 구출 할 수 있습니다.

도움이 되었습니까?

해결책

표기법:

  • 계산은 1에서 시작됩니다
  • l.i 요소입니다 i 목록 l
  • l+m 목록의 연결입니다 l 그리고 m
  • 런은 목록 인 최대 하위 목록입니다. [n,n+1,n+2,...,m] 일부 n 그리고 m ~와 함께 n <= m

그래서 우리는 순열을 받았습니다 p 목록의 [1,2,...,N]. 우리는 분열합니다 p 달리기 r_1,r_2,...,r_M 그렇게 p = r_1+r_2+...+r_M. 그런 다음 순열을 찾고 있습니다 q 의 [1,2,...,M] 그렇게 r_(q.1)+r_(q.2)+...+r_(q.M) = [1,2,...,N].

예를 들어, if p = [1,3,4,2,5,6], 우리는 가지고 있습니다 N=6, M=4, r_1 = [1], r_2 = [3,4], r_3 = [2] 그리고 r_4 = [5,6]. 이 경우 우리는 필요합니다 q 되려고 [1,3,2,4] ~처럼 r_1+r_3+r_2+r_4 = [1]+[2]+[3,4]+[5,6] = [1,2,3,4,5,6].

주목하십시오 q 정의 당 하나보다 큰 길이의 실행을 포함 할 수 없습니다. 그렇다면, i < M ~와 함께 q.i + 1 = q.(i+1) 따라서 하위 목록 r_(q.i)+r_(q.(i+1)) = r_(q.i)+r_(q.i + 1) 의 [1,2,...,N], 하지만 r_(q.i)+r_(q.i + 1) 또한 의도입니다 p 그것은 그것을 모순합니다 r_(q.i) 그리고 r_(q.i + 1) 실행됩니다.

자, 찾기 위해 q 주어진 a p, 우리는 매핑 데이터 구조의 가용성을 O(1) 숫자와 목록의 삽입 및 조회 O(1) 추가 및 전진 트래버스. 그런 다음 우리는 다음을 수행합니다.

  • 먼저 목록을 구성합니다 runheads = [r_1.1,r_2.1,...,r_M.1]. 이것은 트래버스를 통해 사소하게 수행 될 수 있습니다 p 현재 실행을 유지하는 동안. 이 단계에서 우리는 또한 얻기 위해 발생하는 최대 숫자를 기억합니다. N 마지막에 매핑을 구성합니다 heads 요소와 함께 runheads 열쇠로. 이 단계는 분명합니다 O(n). 가치가 무엇인지는 관련이 없습니다. heads 우리는 단지 런을 사용할 수 있습니다 r_i 키의 값으로 r_i.1.

  • 다음으로 우리는 반복합니다 1 (및 포함) N 가치 유지 k 초기 값으로 1. 각 값에 대해 i 우리는 확인하는지 확인합니다 i 들어 왔습니다 heads. 이것이 우리가 추가하는 경우입니다 i -> k 매핑에 f 그리고 증가 k. 이 단계도 명확합니다 O(n). 돌아올 수 있습니다 q 에게 p 추가 매핑을 저장할 수도 있습니다 rev ~와 함께 k -> i 또는 k -> runheads(i) 여분의 Big-O 비용없이.

  • 마지막으로 우리는 매핑을 적용합니다 f 요소에 runheads 얻기 위해 q. 다시 O(n).

예를 들어 설명하기 위해 우리는 사건을 살펴 봅니다. p = [1,3,4,2,5,6].

  • 첫 번째 단계에서 우리는 얻는다 runheads = [1,3,2,5], N=6 그리고 heads = { 1 -> [1], 3 -> [3,4], 2 -> [2], 5 -> [5,6] }.

  • 두 번째 단계에서는 우리가 무언가를 해야하는 4 가지 사례입니다. 1, 2, 3 그리고 5. 이러한 경우에 우리는 가치가 있습니다 k 그것은 1, 2, 3 그리고 4, 각각. 이것은 그것을 의미합니다 f 될거야 { 1 -> 1, 2 -> 2, 3 -> 3, 5 -> 4 }. (그리고 rev 할 것입니다 { 1 -> 1, 2 -> 2, 3 -> 3, 4 -> 5 } 또는 { 1 -> [1], 2 -> [2], 3 -> [3,4], 4 -> [5,6] }, 당신이 저장하기로 선택한 것에 따라.)

  • 얻기 위해 q 우리는 계산합니다 map(f,runheads) 그게 [f(1),f(3),f(2),f(5)] 또는 동등하게 [1,3,2,4].

따라서 실수를하지 않았고 데이터 구조가 위의 요구 사항을 충족하는 경우이 솔루션은 O(n). 실제로는 실제로 자신의 사용에 더 유용 할 수 있습니다 (O(n*log(n))) 해결책. 당신이 큰 경우 p 그러나 몇 번의 달리기만으로 정렬합니다 runheads 이를 사용하여 매핑을 구축하는 것이 더 효율적일 수 있습니다. 나는 그것을 생각한다 p 이것이 사실이되기 위해서는 상당히 큰 일이 필요합니다.

다른 팁

SLEFIFICATON 용 편집

1 단계 : 알고리즘을 실행하지만 하나의 해시 테이블 만 생성하는 대신 세트의 헤드에 의해 색인 된 해시 테이블 (D1)을 생성합니다 (예 : 3) 및 목록에 매핑됩니다. (L1) 세트 자체와 함께

[3;4;6;8;1;2]:

   D1              L1

3 -> [3,4]     1 -> [3,4]

6 -> [6]       2 -> [6]

8 -> [8]       3 -> [8]

1 -> [1,2]     4 -> [1,2]

2 단계 : 나는 당신이 우리가 지금 우리가 당신의 컬렉션을 살펴 봅니다. 주어진 세트에 대해 우리는 그것을 찾은 지수 (L1)와 헤드 값을 가지고 있음을 알 수 있습니다. 올바른 맵 값은 아직 취하지 않은 최소 정수입니다. 예를 들어, [3,4]의 경우 값은 1과 3 사이 여야하며, 1이 이미 사용되었으므로 해당 값은 2입니다. 해당 세트가 존재하면 값, 낮은 값이 항상 취해집니다. 이 예에서 [1,2]는 1에 매핑 되어이 키가 이미 "촬영"됩니다. 따라서 의사 코드에서 :

for (int Current = 1; Current  < L1.Length; Current++)
{
  GetHead(L1[Current]);
  Index = Current;
  While Head > Index
  {
    if D1.Empty(Index)
    {
      D1.Add(Index,D2[Current])
      D1.DeleteIfNotEmpty(Head);
    }
    else
      Index++;
  }
}

예를 들어

  • 우리는 L1-> [3,4]에서 첫 번째 가치를 취합니다 ...
  • 머리를 얻으십시오 = 3
  • 1에서 시작하여 이미 촬영 된 D1 [1]을 조회하여 2로 증가합니다.
  • D1 [2] = [3,4]를 할당하고 d [3]를 삭제하는 D1 [2]를 찾습니다.

그것은 o (n)을 제공하지 않지만 o (n+log (n))와 같은 것을 제공합니다 (첫 번째 단계의 경우 n, 두 번째 단계의 Log (n))

위의 예는 당신을 얻습니다.

1 -> [1,2]
2 -> [3,4]
3 -> [6]
4 -> [8]

이제 [3; 4; 8; 6; 1; 2]가 있다면

1 -> [1,2]
2 -> [3,4]
3 -> [8]
4 -> [6]

원래 배열에서 절대 순서를 사용하고 있기 때문에, 그것이 괜찮은지 또는 6이 색인 3과 8에있는 지수 4에있게되기를 원할 것인지 모르겠습니다.이 경우 L1을 선주문해야 할 것입니다. 로그 (N)에 의해 복잡성을 증가시키는 헤드를 기준으로

사전 주문 해야하는 경우 0 (n+log^2 (n))가 있어야합니다.이 나쁘지 않은 경우 (QuickSort에 O (log n) 주문 L1이 O (log (log n))가 있다고 가정 할 수 있습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top